Идеи реализации

Один из возможных путей реализации программы — прямой перебор семизначных чисел и выбор среди них тех, что обладают «квадратным» свойством — отвергнем сразу. Во-первых, перебор очень большой. Кроме того, не совсем ясно, как производить отбор.

nколичество «квадратных» n-значных номеров
14
222
3134
4824
55073
631231
7192271
81183701

Выберем другой подход. Заметим, что каждый «квадратный» номер начинается с h-значного квадрата, за которым следует ( 7 k ) -значный номер, также обладающий «квадратным» свойством. Иными словами, каждый квадратный номер можно представить в виде конкатенации «головы» и «хвоста», где «голова» — квадрат, а «хвост» — квадратный номер.

Такое рекурсивное свойство квадратных номеров ведёт к рекурсивному алгоритму их построения. Если перебирать все «головы», h-значные квадраты, где 1 h 7 , и к каждой из них приписывать всевозможные «хвосты», t-значные «квадратные» номера, где t = 7 h , мы получим то, что хотим.

Таким образом, удалось свести задачу поиска семизначных номеров к задаче поиска t-значных для всех t, 1 t 7 . Мы оказываемся с ситуации, когда полезно обобщить исходную задачу: вместо поиска 7-значных номеров научим программу искать n-значные для любого целого неотрицательного n. Казалось бы, поставив перед собой более общую задачу, мы добровольно усложняем себе жизнь. В данном случае это не так.

Информатика-54© А. Н. Швец