• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Matura próbna, znajdź ciąg, algorytm.

VPS Starter Arubacloud
0 głosów
1,699 wizyt
pytanie zadane 11 kwietnia 2017 w C i C++ przez Sinnley Stary wyjadacz (12,810 p.)
edycja 11 kwietnia 2017 przez Sinnley

Na maturze próbnej, którą dzisiaj pisałem do zadania był taki podpunkt:

"Znajdź najdłuższy ciąg liczb występujących kolejno po sobie w pliku liczby.txt taki, że największy wspólny dzielnik ich wszystkich jest większy od 1. Jako odpowiedź podaj pierwszy wyraz ciągu, długość ciągu, oraz liczbe. która jest ich największym dzielnikiem"

NP: Dla liczb 3, 7, 4, 6 , 10, 2, 5 odpowiedzią będzie 4, 4, 2.

Pliku niestety nie mam, ale raczej można go sobie nawet wygenerować. Liczby były z zakresu do max 1-100000 , bylo ich 500 i były zapisywane po jednej w linijce, czyli separatorem był enter. Chodzi mi o algorytm. Na maturze pierwszy pomysł, na który wpadłem był strasznie nieoptymalny. Polegał na tym, że sprawdziłem jaka liczba jest największa, a potem wypisywałem najdłuższe ciągi dla każdego możliwego dzielnika, czyli od 2-x, gdzie x to najwieksza liczba. Potem sprawdziłem, który z tych ciągów jest najdłuższy.

Jakie wyjście byłoby optymalne? Bo moje nie dość, że jest nieoptymalne, to jeszcze czasochłonne jest jego napisane. 

1 odpowiedź

0 głosów
odpowiedź 11 kwietnia 2017 przez Aisekai Nałogowiec (42,190 p.)
NWD(a,b,c) = NWD(NWD(a,b),c). O co chodzi? Chodzi o to, żebyś najpierw obliczył NWD dwóch liczb. Potem wykorzystując to NWD, możesz policzyć NWD tych dwóch liczb i następnej. Itd itd. To musiałbyś już odpowiednio napisać. Przynajmniej ja bym to tak zrobił.

Do matury powinieneś umieć algorytm euklidesa, więc to nie będzie dość ciężkie.
komentarz 11 kwietnia 2017 przez Sinnley Stary wyjadacz (12,810 p.)
Zgadza się, ale czy to rozwiąże problem? W końcu warunkiem nie jest jest najdłuższy ciąg, a nie największe NWD. Czy nie prościej będzie znaleźć wpierw najdłuższy ciąg liczb, które w ogóle mają jakikolwiek wspólny dzielnić, a potem dopiero sprawdzić NWD?
komentarz 11 kwietnia 2017 przez Aisekai Nałogowiec (42,190 p.)
Jakbyś miał np liczby:

11, 39916800, 7983360. Najpierw musiałbyś sprawdzić dzielniki: 11 - 11. 39916800 = 11! (1,2,3,...11). 7983360 = 11!/5. Wyszłoby Ci, że masz do 10 dzielników z drugiej liczby i 10 dzielników z trzeciej liczby (bo dopiero by się okazało [i słusznie] że te wszystkie trzy liczby są wielokrotnościami 11). Czyli według Twojego sposobu, musisz najpierw znaleźć wszystkie dzielniki każdej liczby (mniejsze bądź równe najmniejszej z tych liczb), a potem dopiero liczyć jeszcze raz NWD.

 

Przy czym mój sposób, pozwala Ci wykorzystać wcześniej obliczone NWD z dwóch poprzednich liczb. Czyli np jakbyś miał 2, 1024, 2048, najpierw obliczasz NWD(2,1024) = 2, potem obliczasz NWD(2 [bo NWD(2,1024)=2],2048) = 2, zamiast obliczać NWD(1024,2048). Nie szukam żadnych wspólnych dzielników, nie wykonuję zbędnych operacji przy szukaniu NWD, bo używam już wcześniej obliczoną NWD.

Wydaje mi się, że to będzie bardziej optymalne.
komentarz 11 kwietnia 2017 przez Sinnley Stary wyjadacz (12,810 p.)
Może tak, ja od początku mówiłem, że moje rozwiązanie jest nieoptymalne. Bardziej zastanawia mnie sama kwestia jak to ubrać w kod, żeby potem gdzieś sobie te ciągi przechować.
komentarz 11 kwietnia 2017 przez Aisekai Nałogowiec (42,190 p.)
Nie potrzebujesz przechowywać ciągów. Potrzebujesz podać pierwszy wyraz ciągu, długość tego ciągu i NWD. Potrzebujesz tutaj tak naprawdę po 2 zmienne przechowujące wartości dla sprawdzanych i dla maksymalnych. Tzn potrzebujesz zmiennych które by Ci przechowywały:

- index wyrazu ciągu, max długość i NWD.

- Index wyrazu, który rozpoczyna następny ciąg. Np jak masz 2,4,8,3,6,9 to najpierw ustawiasz indeks na 1 (czyli 2), potem dochodzisz do sprawdzenia gdzie NWD dwóch liczb jest równe 1. I przechowujesz w jakiejś innej zmiennej aktualny indeks. Długość dla tego ciągu i NWD.
komentarz 11 kwietnia 2017 przez Aisekai Nałogowiec (42,190 p.)
Jak coś niezrozumiale napisane to napisz, to postaram się to ładniej w słowa ubrać
komentarz 12 kwietnia 2017 przez Sinnley Stary wyjadacz (12,810 p.)
No troszkę to zagmatwane. Najprościej jakbyś napisał fragment kodu, tak to najłatwiej chyba ogarnąć.
komentarz 12 kwietnia 2017 przez Aisekai Nałogowiec (42,190 p.)
To jutro jak nie zapomnę, to napiszę fragment kodu, albo pseudokodu.
komentarz 12 kwietnia 2017 przez Sinnley Stary wyjadacz (12,810 p.)
Jak coś podbije komentarz żeby ci się powiadomienie pojawiło, jeśli nie napiszesz :D
komentarz 12 kwietnia 2017 przez Aisekai Nałogowiec (42,190 p.)
Dobra to tak, masz 6 intów (np. długoscMaxCiagu, dlugoscBadanegoCiagu, indeksNajdluzszegoCiagu, indeksBadanegoCiagu, NWDBadanegoCiagu, NWDNajdluzszegoCiagu). Każdej zmiennej na początku przypisujesz wartość 1. Potem sprawdzasz NWD dwóch liczb. Jeżeli jest różne od 1, to inkrementujesz jedną z nich (odpowiedzialną za przechowywanie informacji o tym jaką długość ma badany ciąg). Robisz tak do czasu aż dojdziesz do momentu gdzie napotkasz na liczbę, której jej NWD i dotychczasowe NWD będzie równe 1. Jeżeli coś takiego będziesz miał, to sprawdzasz czy długość badanego ciągu jest dłuższa od długości maksymalnego ciągu (dlugoscNajdluzszegoCiagu). Jeżeli tak, to to dlugoscNajdluzszegoCiagu=dlugoscBadanegoCiagu, indeksNajdluzszegoCiagu=indeksBadanegoCiagu itd. Jeżeli nie to nic nie robisz. Niezależnie od przypadku dlugoscBadanegoCiagu ustawiasz na 1, indeksBadanegoCiagu ustawiasz na tą liczbę przy której NWD było równe 1, NWDBadanegoCiagu ustawiasz potem.

Możesz dodać dodatkową zmienną która będzie Ci przechowywała informacje odnośnie tego, którą liczbę teraz badasz, np. nrLinii (bo to masz w liniach), indeks. Inkrementujesz to po tym jak już pobierzesz dane z pliku.

Podobne pytania

0 głosów
2 odpowiedzi 1,292 wizyt
pytanie zadane 28 grudnia 2016 w C i C++ przez Krystek102 Bywalec (2,440 p.)
–2 głosów
0 odpowiedzi 737 wizyt
0 głosów
2 odpowiedzi 1,465 wizyt
pytanie zadane 22 kwietnia 2020 w Algorytmy przez ritit Nowicjusz (150 p.)

92,454 zapytań

141,262 odpowiedzi

319,095 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...