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, botów: 0