[C++] Suma częściowa ciągu
-
- Użytkownik
- Posty: 874
- Rejestracja: 4 paź 2010, o 08:16
- Płeć: Mężczyzna
- Lokalizacja: wszedzie
- Podziękował: 248 razy
- Pomógł: 10 razy
[C++] Suma częściowa ciągu
Jak napisać program który wczyta ciąg liczb całkowitych i wypisze pierwszą powtarzającą się sumę częściową ciągu .
Ostatnio zmieniony 31 mar 2012, o 23:13 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[C++] Suma częściowa ciągu
jeśli wiadomo, że sumy będą małe, to najłatwiej i najszybciej stworzyć tablicę typu bool i wszędzie powstawiać false.. idziemy od początku ciągu sumując kolejne wyrazy do zmiennej s i wstawiając na s-tym miejscu w tablicy true.. jeśli w momencie w którym chcemy wstawić true ta wartość już tam jest, to znaleźliśmy naszą szukaną sumę..
jeśli nie wiadomo czy sumy będą małe, a chcemy mieć łatwe rozwiązanie, to częściowe sumy pamiętamy w liście, a lepiej w drzewie BST.. (i za każdym razem wstawiając sumę patrzymy czy przypadkiem jej tam nie ma - jeśli jest to znaleźliśmy)
jeśli chcemy mieć super rozwiązanie to zamiast drzewa BST używamy zbalansowanego drzewa, albo lepiej tablicy z haszowaniem..
jeśli nie wiadomo czy sumy będą małe, a chcemy mieć łatwe rozwiązanie, to częściowe sumy pamiętamy w liście, a lepiej w drzewie BST.. (i za każdym razem wstawiając sumę patrzymy czy przypadkiem jej tam nie ma - jeśli jest to znaleźliśmy)
jeśli chcemy mieć super rozwiązanie to zamiast drzewa BST używamy zbalansowanego drzewa, albo lepiej tablicy z haszowaniem..