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ę.
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.
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;
}
#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;
}
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;
}
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
Daim123 napisał(a):
Wczytujemy ciąg znaków, dopóki użytkownik odpowiada T na pytanie: Czy
podjeszkolejny znak(T-tak)? Wykorzystaj stos i
Jeżeli użytkownik odpowie na to pytania twiedząco, to należy psychiatrę wzywać.