Każdą dodatnią liczbę całkowitą n można reprezentować jako sumę kwadratów dodatnich liczb całkowitych. Może istnieć wiele różnych takich sum.
Długością reprezentacji (kwadratowej) nazywamy liczbę składników sumy.
Jedną z metod otrzymywania krótkich reprezentacji kwadratowych jest metoda zachłanna, w której w każdym kroku jako kolejny składnik sumy bierze się największy możliwy kwadrat liczby całkowitej gwarantujący, że suma nie przekracza n. Ta metoda nie zawsze znajduje najkrótsze reprezentacje.
Napisz algorytm, który dla danej dodatniej liczby całkowitej n obliczy długość jej reprezentacji kwadratowej wyznaczanej metodą zachłanną.
Uwaga!
W zapisie algorytmu możesz korzystać tylko z instrukcji sterujących, operatorów arytmetycznych (dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia), operatorów logicznych, porównań i instrukcji przypisywania lub samodzielnie napisanych funkcji i procedur wykorzystujących powyższe operacje. Zabronione jest używanie funkcji wbudowanych, dostępnych w językach programowania, zwłaszcza funkcji pierwiastek.
liczby.txt koncerty.txt miasta.txt napisy.txt zespoly.txt 5a.jpg
Długością reprezentacji (kwadratowej) nazywamy liczbę składników sumy.
Jedną z metod otrzymywania krótkich reprezentacji kwadratowych jest metoda zachłanna, w której w każdym kroku jako kolejny składnik sumy bierze się największy możliwy kwadrat liczby całkowitej gwarantujący, że suma nie przekracza n. Ta metoda nie zawsze znajduje najkrótsze reprezentacje.
Napisz algorytm, który dla danej dodatniej liczby całkowitej n obliczy długość jej reprezentacji kwadratowej wyznaczanej metodą zachłanną.
Uwaga!
W zapisie algorytmu możesz korzystać tylko z instrukcji sterujących, operatorów arytmetycznych (dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia), operatorów logicznych, porównań i instrukcji przypisywania lub samodzielnie napisanych funkcji i procedur wykorzystujących powyższe operacje. Zabronione jest używanie funkcji wbudowanych, dostępnych w językach programowania, zwłaszcza funkcji pierwiastek.
