Zadanie gąsienica

1

Zadanie: Dany jest ciąg n liczb naturalnych. Napisz program znajdujący długość najdłuższego podciągu niemalejącego, stosując algorytm gąsienicy. Wypisz elementy tego podciągu.

Bardzo proszę o jakiś schemat działania, który pomoże mi to napisać, oczywiście bez kodu proszę.

3

Nie wiem czy to jest algorytm gąsienicy, ale ja to najprościej widzę tak:
Masz tablicę wypełnioną ciągiem liczb naturalnych.
Dwie zmienne min i max przechowujące pozycje elementów najdluzszego podciagu. Tymczasowe tmin i tmax.
Pętle for przechodzącą przez wszystkie elementy tablicy.
W pętli for operujesz tymczasowa zmienna tmin i tmax, jak następny element jest wiekszy rowny od tymczasowej tab[tmax] to ustawiasz tmax na index tego elementu. Jak mniejszy to tymczasowe tmin i tmax ustawiasz na nowy element wcześniej sprawdzając czy tymczasowa roznica tmax tmin jest wieksza od roznicy max i min wtedy tymczasowe przypisujesz do min i max.
Po przejsciu całej tablicy zostaje ci tylko w petli wyswietlic elementy tablicy od min do max.

0

Dziękuję za odpowiedzi, napisałem na razie taki kod, w którym czegoś brakuje

using namespace std;

int main()
{

    /*int T[12] = {3,4,5,6,4,2,2,1,9,1,0,7};*/
    
    int n;
    
    cout<<"Podaj ile masz liczb: ";
    cin>>n;
    
    int * T = new int[n];
    for(int i=0; i<n; i++)
    {
        cin>>T[i];
    }
    
    int min = 0;
    int max = 0;
    int tmin = 0;
    int tmax = 0;
    for(int i=0; i<n; i++)
    {
     if(T[tmax]<=T[i])
     {
         tmax = i;
     }
        else if(T[tmin]>=T[i])
        {
            if((tmax - tmin)>(max-min))
            {
                max = tmax;
            min = tmin;
            }
                tmin = i;
            tmax = i;
        }
        
    }
    
    for(int i = min; i<=max; i++)
    {
        cout<<T[i]<<" ";
    }
    
    
    delete [] T;
    
    return 0;
}
1
#include<iostream>
using namespace std;

int main()
{

    //int T[12] = {3,4,5,6,4,2,2,1,9,1,0,7};

    int n=0;

    cout<<"Podaj ile masz liczb: ";
    cin>>n;

    int * T = new int[n];
    for(int i=0; i<n; i++)
    {
        cin>>T[i];
    }

    int min = 0;
    int max = 0;
    int tmin = 0;
    int tmax = 0;
    for(int i=0; i<n; i++)
    {
    	
     	if(T[i]>=T[tmax])
     	{
     	
         tmax = i;
     	}
     	else
     	{
     		if((tmax-tmin)>(max-min))
     		{
     			min = tmin;
     			max = tmax;
			 }
     	 tmin = i;
     	 tmax = i;
		}

    }
    
	if((tmax-tmin)>(max-min))
     		{
     			min = tmin;
     			max = tmax;
			 }

    for(int i = min; i<=max; i++)
    {
        cout<<T[i]<<" ";
    }

    delete [] T;

    return 0;
}
1

Przecież nikt ne kazał tego podciągu drukować, więc wystarczy:

#include <iostream>
using namespace std;

int main()
{
   cout<<"Podawaj liczby <Ctrl-Z><Enter> - Koniec"<<endl;
   size_t best=0,curr=0;
   for(int prev=0,value=0;cin>>value;prev=value)
   {
      if((prev<=value)||(!curr)) ++curr;
      else
      {
          if(best<curr) best=curr;
          curr=1;
      }
   }
   cout<<"Maks: "<<best<<endl;
   return 0;
}
0

Dobrze, a teraz mam takie zadanie:

Wczytujemy ciąg znaków, dopóki użytkownik odpowiada T na pytanie: Czy podjesz kolejny znak(T-tak)? Wykorzystaj stos i kolejkę z biblioteki STL przy sprawdzaniu, czy ten ciąg jest palindromem.

Również proszę jedynie o wskazówki bez kodu

1
Daim123 napisał(a):

Wczytujemy ciąg znaków, dopóki użytkownik odpowiada T na pytanie: Czy podjesz kolejny znak(T-tak)? Wykorzystaj stos i

Jeżeli użytkownik odpowie na to pytania twiedząco, to należy psychiatrę wzywać.

1 użytkowników online, w tym zalogowanych: 0, gości: 1