kto zrobil zadanie z ciagiem. porownajcie

[Gość: Jacek86]

witam. maturka ogolnie do bani!! za malo czasu !
ja w sumie to tylko z programowania czuje sie jako tako. i tylko to ruszylem.
napisALEM PROGRAM LICZACY jakies tam sumy (najlepsze ?) ciagow. nie pamietam
jak to sie nazywalo.
chcialbym porownac to z kims kto tez to napisal.
chodzio mi glownie o optymalicacje bo komp wieszal sie jak liczyl sume
tego ostatniego ciagu ktory mial 10 000 wyrazow!

przedstawe tylko glowna procedure liczaca sume, pomijajac wczytywanie danych
i te inne pierdoly.
napisalem to w ten sposob:


var
ciag : array[0..9999] of integer;

dl:integer; {dlugosc fragmentu sprawdzanego ciagu}
j:integer; {dlugosc calego ciagu np 10 000}
i:integer; {indeksowa polozenia w ciagu}
suma1,suma2:longint; {porownywane sumy ciagow}

begin

suma1:=0;
suma2:=0;

for dl:=1 to j do {sprawdzaj dla wszystkich mozliwych dlugosci}
begin
for i:=0 to j-dl do {sprawdzaj poczawszy od kazdego wyrazu, j-dl -
zeby nie "wychodzilo" za tablice}
begin
suma1:=0; { zeruj sume przed kazdym nowym sprawdzaniem}
for n:=i to i+dl-1 do {dodawaj kolejne wyrazy od i-tego do i+dl.
-1 po to zeby dlugosc sie zgadzala}
begin
suma1:=suma1+ciag[n]; {dodawaj kolejne wyrazy}
end;
if suma2<suma1 then suma2:=suma1; {sprawdz czy obliczona suma
jest wieksza od poprzedniej,
jezeli tak to zastap}
end;

END;

ostatecznie najwiekasza wartosc zostaje zapisana w zmiennej suma2.

to moze byc zawile. moze ktos podszedl do tego podobnie tylko inaczej
zapisal. dlatego wytlumacze.
procedura liczy sumy ciagow o wszystkich mozliwych dlugosciach (1-1000),
sprawdzajac po kolei z wszystkich mozliwych
pozycji ciagu. nie umiem prosciej wyjasnic.

pisze ten algorytm z pamieci wiec moze byc jakis blad bo pisze na forum a nie
w pascalu. ale ten na maturce dzialal. sprawdzalem bo zrobilem swoj testowy
ciag i znalem jego najlepsza(?) sume.
liczylo jak trza. chodzi mi o to ze ten algorytm zapetla sie tysiace razy i
dziala bardzo woooolno.
ktos rozwiazal to szybciej ?

[Gość: Kisu]

Napisać program to nie problem - gorzej go opisać;-) Chodzi Ci o zadanie 5?!
Tam nie było żadnej sumy. Chyba, że z I arkusza zad.1 ? W każdym bądź razie mam
zrobione oby dwa zadania.

[Gość: Jacek]

kurde nie pamietam to bylo chyba 2 z 2 arkusza
i tak maturke zwalilem, zaintrygowalo mnie po prostu jak to zrobic szybciej.
jak masz to moze pochwalisz sie swoim algorytmem ?
bo moj za nic nie mogl sie wyrobic z liczeniem tych 10 000 wyrazow. mam tylko
te sumy 2 pierwszych ciagaw.

[Gość: Kisu]

Najpierw trzeba było znaleźc liczę "najlepszą" (czy jakoś tak). To było proste
czytanie danych z pliku do tablicy, a następnie szukanie max sumy wyrazów
sąsiadujących (śmignęło w 0.0000001s). Drugi był trudniejszy. Tu trzeba było
zliczyć która liczba występuje najczęściej. Można to było zrobić metodą taką
samą jak sortowanie przez zliczanie (poszukaj w necie o tym info). Też śmignęło
i nie rozumiem tego polecenia "Oszacuj szybkość programu"!

[Gość: Kapela]

nie wyrazow sasiadujacych, tylko np na 4 wyrazy to bylo
1
1+2
1+2+3
1+2+3+4
2
2+3
2+3+4
3
3+4
4

to cos nie moglo w 0.0000001 s śmignąć :P chyba ze pracowałeś na jakimś
zajebistym klastrze :]

[Gość: Jacek86]

no tak. trzeba bylo policzyc sumy sasiadujących ze sobą wyrazow ciagu. ale
trzeba bylo sprawdzic wszystkie mozliwe kombinacje. wyrazow ciagu o dlugosci
1000 jest 1, tych o dlugosci 9999 jest 2, 9998 jest 3, 9997 jest 4, itp...
program musial policzyc sume wszystkich tycgh wyrazow aby sprawdzic ktora jest
najwieksza. samo liczenie sumy kilku tysiecy liczb troche trwa, nie mowiac juz
o tym ze algorytm powtarza to tysiace razy. jezeli u ciebie dzialalo w 0,000001
to albo mieliscie wyje..e kompy, albo cos ominales. No chyba ze zajebisty z
ciebie optymalizator :) napisz szwoj algorytm to pogadamy.

Chyba ja

[Gość: Kali]

LUDZIE! Nie pieprzcie, że TRZEBA wszystko sprawdzać. Tutaj na prawdę daje się
napisać program liniowy, który się wykona szybko i sprawnie. A dróga sprawa
jest taka, że powszechnie się wierzy, że optymalizacja danego algorytmu skraca
czas o najwyżej kilka %...

[Gość: Kali]

Daję jakieś 80% szans, że "oszacuj szybkość programu" to jest to samo co podaj
jego złożoność, czyli jaką ma granicę:
log o podstawie n z (ilość poleceń wykonywanych przez program)
gdzie n to ilość danych wejściowych dążące do nieskończoności.

[Gość: Jacek86]

to w koncu jak obliczyc? jak sie liczy granice log n X? wydaje mi sie ze jezeli
n dozy do nieskonczonosci a X jest stale to wartosc logarytmu dazy do zera. byc
moze sie myle bo nigdy nie liczylem granicy logarytmu. ale tak na zrowy rozum
wynika. czy moze n jest stale ?? bo program nie ma chyba nieskonczonej liczby
danych? a jezeli tak to jak obliczyc ta ilosc danych ? jak to trza bylo zrobic
praktycznie a nie teoretycznie ??

[Gość: Kali]

Dobra, sorki za mówienie o tej granicy, łatwiej powiedzieć jak to jest w
praktyce:
Program wykona ileś tam operacji (pojedyńczych linijek w kodzie) w zależności
od ilości danych wejściowych - n. To zazwyczaj jest jakiś wielomian (zależność
ilości operacji, od n). Bierzemy jego stopień i mówimy, że algorytm ma
złożoność n^stopień wielomianu.
I tak na przykład algorytm:
for i:=0 to n do
begin
...
end; ma złożoność liniową (n^1).
Algorytm
for i:=0 to n do
for j:=0 to n do
begin
...
end;
ma złożoność n^2, bo wnętrze pętli (...) zostanie wykonane n^2 razy.
Oczywiście sprawa się kąplikuje, jak wewnątrz pętli są jakieś if'y i tak dalej.
Jednak w przypadku prostych algorytmów zazwyczaj da się "na oko" ocenić
złożoność. Tak na przykład podany algorytm sprawdzania wszystkich możliwych
sum, ma złożoność n^2, bo de facto robi:
Dla wszystkich długości sum (od 1 do n)
Dla wszystkich możliwych początków sum
zsumuj i sprawdź.
Oczywiście dla sum długości n możliwych początków jest jeden (pierwszy
element), ale jeżeli policzymy ile razy w zależności od n zostanie wykonane:
"zsumuj i sprawdź", to wyjdzie:
n*(n-1)/2=n^2/2 - n/2, stopień tego wielomianu to 2, więc złożoność n^2.
Pozdrawiam.

[Gość: Tom]

U mnie też wieszał się na dane5-3.txt. Pisałem w C++

[bracishek]

To ja to zintepretowałem tak jak Kapela.. Sąsiadujące wyrazy zrozumiałem, jako
dwa sąsiadujące.. I wg. mnie tak właśnie to powinno wyglądać. Bo nie rzucali by
zadanka, które by się wykonywalo pół h..

Za tydzień klucz będzie to zobaczymy o co tak naprawdę chodziło.

[Gość: Tomo]

Hmm, napisali wyraźnie że SĄSIADUJĄCE wyrazy, a przez to dla ciągu X Y Z
rozumiem wyrazy X,X+Y,Y,X+Y+Z,Y+Z,Z no i tak po kolei się szybko wykonywało...
Nie wiem czy mam dobrze bo z tymi maturami już h.. wiadomo ale napisali że suma
sąsiednich nie wszystkich

[Gość: Tomo]

A że nikt nie napisał żadnych wyników to u mnie wyszło z algorytmem (dla tych
pierwszych ciągów dobrze sie sprawdzał dla pliku 5-1.txt = 46, dla 5-2.txt 49 i
dla 5-3.txt chyba 69. Jeszcze raz mówię żeby się tym nie sugerować :)

[Gość: muzgus]

ja piszę maturę za rok, ale coś takiego ze znajomym wymyśliłem przed chwilą:

-przy wczytywaniu danych od razu sumujemy sąsiadujące wyrazy o tych samych
znakach, otrzymując tablicę, na której są dane +, -, +, - (to było nawet
podpowiedziane), jeżeli pierwszy lub ostatni wyraz jest ujemny, to go ucinamy.
-robimy pętlę, o indeksie i, w niej następną pętlę, o indeksie Jedziemy po całej
tablicy indeksem i, dodając do siebie wyrazy kolejne, gdzie pierwszy ma indeks
dane[i], a każdy następny dane[i+j] (to już w tej drugiej pętli). Jeżeli
aktualna suma jest większa od największej, to zapisujemy ją.

o ile wiem, to plik największy z danymi miał 44kb, co daje maksymalnie 22000
liczb. Liczba iteracji to n^2, czyli 22000^2, czyli 484000000. To jest
praktycznie nic dla procesora 1GHz.

jest jakiś błąd w tym rozumowaniu?

chyba ja

[Gość: Kali]

W tym co napisał Mózgus błędu nie ma, ale to jest brute force i ma złożoność
n^2.
Mój pomysł jest taki:
WEJŚCIE: n - ilość danych, dane - tablica o indexach od 0 do n-1
ZMIENNE: suma=0, k=0, max=dane [0]
PROGRAM:
jeżeli suma>max to max=suma
suma=suma+dane [k]
jeżeli k=n-1 to zakończ
k=k+1
jeżeli suma<=0 to k=k+1 i suma=0
wróć do początku programu
WYJŚCIE: w max jest największa możliwa suma.
Złożoność tego jest liniowa.
Pozdrawiam.

[Gość: Kali]

SORKI, mały błąd :)
W tym co napisał Mózgus błędu nie ma, ale to jest brute force i ma złożoność
n^2.
Mój pomysł jest taki:
WEJŚCIE: n - ilość danych, dane - tablica o indexach od 0 do n-1
ZMIENNE: suma=0, k=0, max=dane [0]
PROGRAM:
suma=suma+dane [k]
jeżeli suma>max to max=suma
jeżeli k=n-1 to zakończ
k=k+1
jeżeli suma<=0 to k=k+1 i suma=0
wróć do początku programu
WYJŚCIE: w max jest największa możliwa suma.
Złożoność tego jest liniowa.
Pozdrawiam.

[Gość: cienki]

To może mi ktoś wytłumaczy co oznacza ten podkreślony i wytłuszczony wyraz
SĄSIEDNICH ? Bo suma sąsiednich to była by tego z prawej z lewej i tego w środku.
A w przykładzie 4 suma to suma wszystkich liczb :|

PS. może się mylę, jeśli tak to proszę o wytłumaczenie.
A tak w ogóle to aa sąsiada można uważać nie tylko tego z kim się ma wspólny
płot ;) sąsiad pojęcie względne :P

[Gość: Kali]

Niezależnie od słowa, był podany przykład i wszystko (w sumie ;) tłumaczył. A
mianowicie chodzi o sumę wyrazów o indeksach z pewnego przedziału, czyli o sumę
a(i)+a(i+1)+a(i+2)+...+a(k-1)+ak, dla 0<=i<=k<n.

[Gość: cienki]

czyli wyraz "sąsiednich" był raczej nie na miejscu. Może to ja tylko szukam
dziury w całym i nie rozumiem tego, ale wydaje mi się to nie sprecyzowane, co
innego mówi przykład a co innego treść polecenia.

[Gość: Kali]

hmm
1) często w różnych zadaniach jest "cośtam (suma/iloczyn) SĄSIEDNICH wyrazów" i
zazwyczaj jest to rozumiane tak jak tutaj
2) nawet jeżeli intepretacja jaką sugeruję nie była naturalna, to jednak
sformuowanie było conajwyżej "niejasne", a nie "jednoznacznie mylące", a jak
sformuowanie jest niejasne, to się patrzy w przykład... i się wie.

[Gość: Jacek86]

dobrze gada , polac mu

hmm nie bardzo rozumiem

[Gość: Jacek86]

wybacz ale nie bardzo rozumiem ten algorytm( moze dlatego ze niedawno wstalem:))
ale bylbym wdzieczny gdybys zapisal to w jakims jezyku. byc moze masz racje ale
jakos nie moge sobie wbic do glowy tego rozumowania.
jezeli chodzi o spor ktore to sa sasiadujace wyrazy:
suma sasiadujacych wyrazow to nie tylko suma wyrazow w otoczeniu np wyrazu Y
czyli X+Y+Z, ale chodzi tu o wszystkie mozliwe sasiadujace wyrazy (tak jak bylo
w przykladzie) czyli nie sumuje sie wyrazow w otoczeniu wyrazu n czyli (n-1)+n+
(n+1), ani tez 2 sasiadujacych tylko wszystkie mozliwe kombinacje sasiednich
wyrazow o dlugosci od 1 do max dlugosci ciagu. tak wynikalo z przykladu !! a w
ogole sa gdzies do tego jakies odpowiedzi ?? to moze zobaczymy jak to powinno
wygladac profesjonalnie (:P)

[Gość: jm]

Też wpadłem na ten algorytm. Napisany w C wygląda tak:

tab[] to tablica z elementami ciągu, j to jej długość, tmp to zmienna pomocnicza.

tmp=suma=0;

for (i=0; i<j; i++) {
tmp+=tab[i];
if (!(tmp > 0)) {
tmp=0;
continue;
}
if (tmp > max)
max=tmp;
}

Po zakończeniu pętli w max jest najlepsza suma.

Złożoność O(n).

[Gość: Kali]

Ano zgadzam się. Za to w tej implementacji wprost widać jego złożoność: liniowa.
Inne pytanie jest dlaczego ten algorytm działa. Podstawowe spostrzeżenie jest
takie:
mamy ciąg i wiemy, że gdzieś w jego środku jest ta nalepsza suma (oznaczona NS).
Jeżeli pierwszy wyraz jest ujemny, to niezależnie gdzie jest NS, ten wyraz do
niej NIE należy.
Jeżeli suma pierwszych dwóch wyrazów jest ujemna, to niezależnie gdzie jest NS,
te dwa wyrazy nie należą do NS.
Jeżeli ... i tak dalej.
Tyle, że my w pewnym momencie wkroczymy w NS, nie jest tak, że stale jesteśmy
przed nią. Dlatego w trakcie tego sprawdzania, czy aktualna suma jest ujemna,
trzeba wybierać dotychczas największą z uzyskanych sum i zapamiętać. Po
przejściu przez całą tablicę sprawdzimy wszystkie "sensowne" sumy i spośród
nich wybierzemy najlepszą.

[pante]

zrobiłem to zadanie mniej więcej tak:

var
i,j,n:integer;
a:array[1..11111] of shortint;
suma,najsuma:longint;
(...)
najsuma:=0;
for i:=1 to n-1 do
begin
suma:=0;
for j:=i to n do
begin
inc(suma,a[j]); if suma>najsuma then najsuma:=suma;
end;
end;
suma:=a[n]; if suma>najsuma then najsuma:=suma;
writeln(najsuma);

Wyniki: 106, 139 i 1342 (dla tych 10001 liczb program potrzebował kilku sekund).
Myślicie, że tak jest dobrze?

[Gość: Kali]

Nie jest to program idealny, ale pomysł na moje oko idzie.
Wciąż jednak (tak jak wiele na tym forum) program ten ma złożoność n^2, czyli
za dużą. Da się zrobić w czasie zależnym od n liniowo.
Ale:
1) "najsuma:=0;" a co jak wszystkie wyrazy są ujemne? Wtedy najsuma będzie
przez cały czas 0... Powinno być na przykład "najsuma:=a[0];".
2) Nie wiem dlaczego Twoja tablica ma aż 11'111 komórek? To już nie błąd, ale
po prostu nie wiem po co...
3) Zamiast wyraz a[n] rozważać osobno, można zrobić tak:
for i:=1 to n do
begin
suma:=0;
for j:=i to n do
begin
inc(suma,a[j]);
if suma>najsuma then
najsuma:=suma;
end;
end;
Ale to już tylko elegancja.

[Gość: Jacek86]

panowie. wg mojego rozumowania powyzszy algorytm liczy sumy n pomniejszych
ciagow. o liczbie wyrazow odpowiednio n, n-1,n-2 itd.
liczy od i-tego wyrazu, zawsze(!)do samego konca. wg tego algorytmu ciagow n
wyrazowych jest 1, n-1 wyrazowych jest 1, n-2 wyrazowych 1, itd. ale na zdrowy
rozum wynika ze jest ich odpowiednio 1,2,3 ...itd. i trza je wszystkie
sprawdzic. moze mi sie juz przez ta fizyke (tak, zdaje) mozg lasuje i dlatego
taki tepy chwilowo jestem. bylbym wdzieczny za komentarz mojego toku
rozumowania. i ewentualne dokladniejsze (o ile sie da :)) wytlumaczenie tego
algorytmu. pozdro

[Gość: Kali]

Liczy faktycznie te sumy, ale w trakcie ich liczenia, przed dodaniem każdego
noweg wyrazu sprawdza, czy AKTUALNA suma, nie jest większa od maxa.

[Gość: Jacek86]

zwracam honor :) faktycznie to dziala. przeoczylem ze ten IF jest w petli :p
a z drugiej strony to Respect, ja bym na to nie wpadl :) niby takie proste a
takie zawile.
pozdro

[pante]

2) Tak mi się wpisało - pięć razy '1' :) Chodziło o to, żeby starczyło na te
10001 liczb z trzeciego pliku z danymi. Ale to przecież w końcu tylko nieco
ponad 1 kB za dużo :)
1) Założyłem, że przynajmniej jeden wyraz jest dodatni (bo takie były dane).
Ale jasne, że żeby było uniwersalnie, powinno być tak, jak mówisz.

Napisałem tu mniej więcej tak, jak na maturze, a tam zrobiłem tak, żeby
działało dla tamtych danych. Poza tym wtedy było bardzo mało czasu na myślenie
i wiele rzeczy mogłoby być lepiej zrobionych.
Cieszę się przynajmniej, że mój sposób daje w co najwyżej kilka sekund jakieś
wyniki, i mam nadzieję, że są dobre i że taki sposób wystarczy. :)

Można tę metodę trochę ulepszyć, np. przy wczytywaniu danych i umieszczaniu ich
w tablicy można liczby dodatnie "grupować" - dodawać te stojące obok siebie i w
tablicy zapisać tę ich sumę jako jedną liczbę dodatnią (zgodnie
z "podpowiedzią" z wcześniejszego podpunktu w tym zadaniu piątym). A gdyby
założyć, że jest przynajmniej jedna liczba dodatnia, to można też w taki sam
sposób grupować liczby<0, a także ignorować zera.
W ten sposób mozna znacznie zmniejszyć rozmiar tablicy (zależy od danych, jak
bardzo) ale chyba i tak jest wciąż n^2.

A jak to zrobić w czasie zależnym od n liniowo?

[Gość: Kali]

#include <stdio.h>

int number;
long suma, max;

#pragma argsused
int main (int argc, char *argv[])
{
while (scanf ("%d\n",&number)!=EOF)
{
suma+=number;
if (suma>max)
max=suma;
if (suma<=0)
suma=0;
}

printf ("%d",max);
return 0;
}

W postach "Chyba ja" jest opisane co to robi i dlaczego działa.

[pante]

Pomysł świetny.
Mam tylko pytanie. Czy tak właśnie zrobiłeś na maturze? (A jeśli nie, to jak?)
Ile czasu na to potrzebowałeś?
No a co z drugim algorytmem?
Pozdrawiam

[Gość: jm]

Ja tak zrobiłem. Potrzebowałem circa 30 minut

[Gość: Kali]

A ja (bo chyba do mnie właśnie kierowałeś pytanie) matury z infy nie pisałem, o
zadaniu powiedział mi kolega, pomyślałem i w sumie jakieś 20 minut stricte
myślenia pewnie to zejąło. Inna sprawa, że robiłem to w domku i bez stresu.
Pozostałe zadania maturalne widziałem, ale nie wyglądały na ciekawe i nie
robiłem.