[C++] Ciąg bitoniczny

[rochaj]

no w końcu jak to będzie, bo problem wydawał się prosty

[Fabix]

Błędem jest odwoływanie się do niezdefiniowanej wartości t[n]. Spróbuj też przeanalizować przypadki równych elementów.

Kurde nie jestem pewien, bo kiedy spróbowałem dynamicznie zadeklarować tablice to dostałem jeszcze więcej błędów, poza tym jak się skompiluje program to on działa dobrze .

[norwimaj]

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>

bool is_bitonic() {
   int prev,next;

   if (! (std::cin >> prev)) return true; // wartosc zwracana dla ciagu pustego

   while (true)
   {
       if (! (std::cin >> next)) return true;
       if (prev > next) {
           prev = next;
           break;
       }
       prev = next;
   }

   while (true)
   {
       if (! (std::cin >> next)) return true;
       if (prev < next) return false;
       prev = next;
   }
}

int main() {

   std::cout << (is_bitonic() ? "YES" : "NO") << std::endl;
   return 0;
}

Nie zakładam, że ciągi muszą być długości co najmniej \(\displaystyle{ 2}\), czyli ciągi \(\displaystyle{ (1)}\) oraz \(\displaystyle{ (1,2)}\) uznaję za bitoniczne. Nie wiem, co ma być zwracane dla ciągu pustego, ale to sobie zamienisz według uznania.-- 19 gru 2014, o 21:13 --

poza tym jak się skompiluje program to on działa dobrze .

Nieprawda. Wynik działania programu jest niezdeterminowany. W ostatnim kroku pętli wychodzisz poza tablicę.

[gryxon]

Kod: Zaznacz cały

int spr(int *tab, int n){
	int i;
	int flaga=0;
	for(i=0;i<n-1;++i){
		if(flaga == 0 && tab[i]>tab[i+1]){++flaga;continue;}
		else if(flaga == 1 && tab[i]<tab[i+1])++flaga;
	}
	if(flaga<2)return 1;
	else return 0;
}
//gdy funkcja zwróci wartość jeden to ciąg spełnia warunki zadania.

Coś takiego nie wchodzi? Problem serio wydaje się łatwy. (wersja dla nierosnącego,niemalejącego.)

[rochaj]

Kod: Zaznacz cały

int spr(int *tab, int n){
	int i;
	int flaga=0;
	for(i=0;i<n-1;++i){
		if(flaga == 0 && tab[i]>tab[i+1]){++flaga;continue;}
		else if(flaga == 1 && tab[i]<tab[i+1])++flaga;
	}
	if(flaga<2)return 1;
	else return 0;
}
//gdy funkcja zwróci wartość jeden to ciąg spełnia warunki zadania.

Coś takiego nie wchodzi? Problem serio wydaje się łatwy. (wersja dla nierosnącego,niemalejącego.)

Ciąg stały nie jest bitoniczny.

[gryxon]

No okej czyli zakładamy wersje dla nierówności ostrych. A co powiesz o ciągu o długości 2?

[rochaj]

No okej czyli zakładamy wersje dla nierówności ostrych. A co powiesz o ciągu o długości 2?

jest bitoniczny

[gryxon]

To chyba wystarczy zmienić znak na nierówności nieostre w warunkach. przetestuj teraz mój poprzedni link (zeedytowałem).

Kod: Zaznacz cały

int spr(int *tab, int n){
   int i;
   int flaga=0;
   for(i=0;i<n-1;++i){
      if(flaga == 0 && tab[i]>=tab[i+1]){++flaga;continue;}
      else if(flaga == 1 && tab[i]<=tab[i+1])++flaga;
   }
   if(n==2 && tab[0]==tab[1])return 0;
   if(flaga<2)return 1;
   else return 0;
}

[norwimaj]

Ciąg stały nie jest bitoniczny.

Jakże nie? Byłoby prościej, gdybyś porządnie zdefiniował ciąg bitoniczny. Trudno jest rozwiązywać zadanie, jeśli się nie rozumie jego treści.

[szw1710]

Więc dla uściślenia proponuję w sensie słabym: ciąg \(\displaystyle{ (a_n)}\) skończony bądź nieskończony nazywamy bitonicznym, jeśli istnieje \(\displaystyle{ n_0}\) takie, że

\(\displaystyle{ a_1\le\dots\le a_{n_0-1}\le a_{n_0}}\) oraz \(\displaystyle{ a_{n_0}\ge a_{n_0+1}\ge a_{n_0+2}\ge\dots}\)

Dopuszczamy do tego ciągi niemalejące. Nierosnące to ciągi bitoniczne z \(\displaystyle{ n_0=1}\).

[rochaj]

Ciąg bitoniczny to ciąg, który najpierw rośnie, a potem maleje. W ciągu bitonicznym \(\displaystyle{ a_1, \ldots , a_n}\) istnieje takie \(\displaystyle{ i \in \{1, \ldots , n \},}\) że ciąg \(\displaystyle{ a_1, \ldots , a_i}\) jest ściśle rosnący, a ciąg \(\displaystyle{ a_i, \ldots, a_n}\) jest ściśle malejący. Ciąg (ściśle) rosnący oraz ciąg (ściśle) malejący są ciągami bitonicznymi.

[szw1710]

Warto jednak badania przeprowadzić dopuszczając nierówności słabe. Przynajmniej tak sądzę.

[Vardamir]

no w końcu jak to będzie, bo problem wydawał się prosty

No w końcu może coś sam zrobisz? Problem jest prosty tylko nie podałeś dokładnych informacji.

Ciąg bitoniczny to ciąg, który najpierw rośnie, a potem maleje. W ciągu bitonicznym \(\displaystyle{ a_1, \ldots , a_n}\) istnieje takie \(\displaystyle{ i \in \{1, \ldots , n \},}\) że ciąg \(\displaystyle{ a_1, \ldots , a_i}\) jest ściśle rosnący, a ciąg \(\displaystyle{ a_i, \ldots, a_n}\) jest ściśle malejący. Ciąg (ściśle) rosnący oraz ciąg (ściśle) malejący są ciągami bitonicznymi.

To powinno się znaleźć w pierwszym poście.

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>
int main() {
   int pvt,result=1;
   std::cin >> pvt;
   for (int x;std::cin >> x;pvt=x)
   {
      if (x<pvt) 
      {
         pvt=x;
         break;
      }
      else if (x==pvt)
      {
      	result=0;
      	break;
      }
   }
   if (result==1)
	  for (int x;std::cin >> x;pvt=x)
	     if (x>=pvt)
	     {
	        result=0;
	        break;
	     }
  std::cout << ((result==1)?"YES":"NO") << std::endl;
  return 0;
}

[gryxon]

Warto jednak badania przeprowadzić dopuszczając nierówności słabe. Przynajmniej tak sądzę.

Kod: Zaznacz cały

int spr(int *tab, int n){
   int i;
   int flaga=0;
   for(i=0;i<n-1;++i){
      if(flaga == 0 && tab[i]>tab[i+1]){++flaga;--i;continue;}
      else if(flaga == 1 && tab[i]<tab[i+1])++flaga;
   }
   if(flaga<2)return 1; // jest bitoniczny
   else return 0; //nie jest
}