Постановка задачи
Составное число называется числом Смита, если сумма его цифр равна сумме цифр всех чисел, образующихся разложением исходного числа на простые множители. Число Смита называется Супер-Числом Смита, если сумма его цифр является числом Смита. Разработать алгоритм и программу поиска супер-числа Смита с номером N, являющегося полным квадратом. (Число называется полным квадратом, если корень квадратный из него является простым числом).
Примечания:
– N является целым положительным числом.
Текстовый алгоритм решения задачи
Таблица 1 – Алгоритм решения
Номер шага | Назначение шага |
Ввод n | |
Smit:=3 | |
i:=1 | |
Начало цикла А. Проверка выполнения условия (i <= n). Если условие истинно, то идти к шагу 5, иначе – к шагу 53 | |
IsSuperSmit:=false | |
Начало цикла B. Проверка выполнения условия (IsSuperSmit = false). Если условие истинно, то идти к шагу 7, иначе – к шагу 52 | |
Smit:=Smit+1 | |
SumCifr:=0 | |
Chislo:=Smit | |
Начало цикла C1. Проверка выполнения условия (Chislo > 0). Если условие истинно, то идти к шагу 11, иначе – к шагу 14 | |
SumCifr:=SumCifr+(Chislo mod 10) | |
Chislo:=Chislo div 10 | |
Конец цикла C1. Идти к шагу 10 | |
Mnozh:=2 | |
Начало цикла D. Проверка выполнения условия (Smit mod Mnozh <> 0). Если условие истинно, то идти к шагу 16, иначе – к шагу 18 | |
Mnozh:=Mnozh+1 | |
Конец цикла D. Идти к шагу 15 | |
Проверка выполнения условия (Smit = Mnozh * Mnozh). Если условие истинно, то идти к шагу 19, иначе – к шагу 50 | |
SumCifrMnozh:=0 | |
Chislo:=Mnozh | |
Начало цикла C2. Проверка выполнения условия (Chislo > 0). Если условие истинно, то идти к шагу 22, иначе – к шагу 25 | |
SumCifrMnozh:=SumCifrMnozh +(Chislo mod 10) | |
Chislo:=Chislo div 10 | |
Конец цикла C2. Идти к шагу 21 | |
SumCifrMnozh:=SumCifrMnozh*2 | |
Проверка выполнения условия (SumCifr = SumCifrMnozh). Если условие истинно, то идти к шагу 27, иначе – к шагу 50 | |
Smit_SumCifr:=SumCifr | |
SumCifr:=0 | |
Chislo:=Smit_SumCifr |
Продолжение – Таблицы 1
Номер шага | Назначение шага |
Начало цикла C3. Проверка выполнения условия (Chislo > 0). Если условие истинно, то идти к шагу 31, иначе – к шагу 34 | |
SumCifr:=SumCifr+(Chislo mod 10) | |
Chislo:=Chislo div 10 | |
Конец цикла C3. Идти к шагу 30 | |
Mnozh:=2 | |
Kol:=0 | |
SumCifrMnozh:=0 | |
Начало цикла E. Проверка выполнения условия (Smit_SumCifr > 1). Если условие истинно, то идти к шагу 38, иначе – к шагу 48 | |
Проверка выполнения условия (Smit_SumCifr mod Mnozh = 0). Если условие истинно, то идти к шагу 39, иначе – к шагу 46 | |
Chislo:=Mnozh | |
Начало цикла C4. Проверка выполнения условия (Chislo > 0). Если условие истинно, то идти к шагу 41, иначе – к шагу 44 | |
SumCifrMnozh:=SumCifrMnozh +(Chislo mod 10) | |
Chislo:=Chislo div 10 | |
Конец цикла C4. Идти к шагу 40 | |
Kol:=Kol+1 | |
Smit_SumCifr:=Smit_SumCifr div Mnozh. Идти к шагу 47 | |
Mnozh:=Mnozh+1 | |
Конец цикла E. Идти к шагу 37 | |
Проверка выполнения условия ((SumCifr = SumCifrMnozh) and (Kol > 1)). Если условие истинно, то идти к шагу 49, иначе – к шагу 50 | |
IsSuperSmit:=true | |
Конец цикла B. Идти к шагу 6 | |
i:=i+1 | |
Конец цикла А. Идти к шагу 4 | |
Вывод Smit | |
Останов |
Структура данных
Таблица 3 – Данные
Элементы данных | Рекомендуемый тип | Назначение |
n | Integer | Номер искомого числа |
Smith | Integer | Хранение проверяемого числа |
Smit_SumCifr | Integer | Хранение суммы цифр проверяемого числа, используется при проверке на то, является ли сумма цифр числом Смита |
Chislo | Integer | Буферная переменная, используемая при расчете суммы цифр некоторого числа |
Mnozh | Integer | Буферная переменная, хранящая значение одного из простых множителей некоторого числа |
SumCifr | Integer | Буферная переменная, хранящая сумму цифр некоторого числа |
SumCifrMnozh | Integer | Буферная переменная, хранящая сумму цифр простых множителей некоторого числа |
Kol | Byte | Счетчик количества простых множителей некоторого числа |
IsSuperSmit | Boolean | Логическая переменная, обозначающая, что проверяемое число это супер-число Смита являющееся полным квадратом |
i | Byte | Счетчик цикла |
Схема алгоритма решения задачи по ГОСТ 19.701_90
Рисунок 1– Графическая схема алгоритма(часть 1)
Рисунок 2– Графическая схема алгоритма(часть 2)
Рисунок 3– Графическая схема алгоритма(часть 3)
Рисунок 4– Графическая схема алгоритма(часть 4)
Рисунок 5– Графическая схема алгоритма(часть 5)
Приложение А
(обязательное)
Исходный код программы
Program Вариант_20;
{ Краткое условие.
Дан номер супер-числа Смита,
являющегося полным квадратом,
необходимо найти это число. }
{$APPTYPE CONSOLE} // консольная программа
Uses
{Объявление библиотек}
SysUtils, // системная библиотека
windows; // библиотека для работы с консолью
Var
{Объявление переменных}
N, Smit, Smit_SumCifr, Chislo: Integer;
Mnozh, SumCifr, SumCifrMnozh: Integer;
IsSuperSmit:Boolean;
i,Kol:byte;
Begin
Try
{Настройка параметров консоли}
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
{Ввод данных}
write('Введите номер искомого числа(0<n<13): ');
readln(n);
{Проверка входных данных}
if (n <= 0) then writeln('Некорректные данные.')
else
begin
{Поиск Супер-Числа Смита с номером n,
являющегося полным квадратом (цикл A)}
Smit:=3;
for i:= 1 to n do
begin
{Поиск i-того Супер-Числа Смита,
являющегося полным квадратом (цикл B)}
IsSuperSmit:=false;
while not(IsSuperSmit) do
begin
Smit:=Smit+1;//задание проверяемого числа
{ Вычисление суммы цифр
проверяемого числа (цикл С1) }
SumCifr:=0;
Chislo:=Smit;
while Chislo > 0 do
begin
SumCifr:=SumCifr+(Chislo mod 10);
Chislo:=Chislo div 10;
end;
{ Поиск простых множителей
проверяемого числа (цикл D) }
Mnozh:=2;
while (Smit mod Mnozh <> 0) do
Mnozh:=Mnozh+1;
{ Проверка на то является ли
проверяемое число полным квадратом }
if Smit = Mnozh * Mnozh then
begin
{ Вычисление суммы цифр простых
множителей проверяемого числа (цикл С2) }
SumCifrMnozh:=0;
Chislo:=Mnozh;
while Chislo > 0 do
begin
SumCifrMnozh:=SumCifrMnozh+(Chislo mod 10);
Chislo:=Chislo div 10;
end;
SumCifrMnozh:=SumCifrMnozh*2;
{ Проверка на то является ли
проверяемое число - числом Смита }
if (SumCifr = SumCifrMnozh) then
begin
{ Проверка на то является ли найденное
число Смита - Супер-Числом Смита }
{ Вычисление суммы цифр нового числа
(новое число - это сумма цифр
проверяемого числа) (цикл С3) }
Smit_SumCifr:=SumCifr;//получение нового числа
SumCifr:=0;
Chislo:=Smit_SumCifr;
while Chislo > 0 do
begin
SumCifr:=SumCifr+(Chislo mod 10);
Chislo:=Chislo div 10;
end;
{ Поиск суммы цифр простых множителей
нового числа и их количества (цикл E) }
Mnozh:=2;
Kol:=0;
SumCifrMnozh:=0;
while Smit_SumCifr > 1 do
begin
if Smit_SumCifr mod Mnozh = 0 then
begin
{ Увеличение суммы цифр
множителей (цикл C4) }
Chislo:=Mnozh;
while Chislo > 0 do
begin
SumCifrMnozh:=SumCifrMnozh+(Chislo
mod 10);
Chislo:=Chislo div 10;
end;
{ Подсчет количества множителей }
Kol:=Kol+1;
Smit_SumCifr:=Smit_SumCifr div Mnozh;
end
else Mnozh:=Mnozh+1;
end;
{ Проверка на то является ли
новое число - Числом Смита }
if (SumCifr = SumCifrMnozh) and
(Kol > 1) then
IsSuperSmit:=true;
end;
end;
end;
end;
{ Вывод найденного числа }
writeln('Найденное число: ',Smit);
end;
readln;
{ Главная проверка корректности данных }
Except
on E: Exception do
begin
writeln('Некорректные данные.');
readln;
end;
end;
End.
Приложение Б
(обязательное)
Тестовые наборы
Группа тестов 1
Тестовые ситуации: Наличие ответа
Тест 1.1
Тестовая ситуация: N<=10
Исходные данные: 7
Ожидаемый результат: 124609
Полученный результат:
Рисунок 6—Тест 1.1
Тест 1.2
Тестовая ситуация: N>10[1]
Исходные данные: 11
Ожидаемый результат: 1190281
Полученный результат:
Рисунок 7—Тест 1.2
Группа тестов 2
Тестовые ситуации: Некорректные данные
Тест 2.1
Тестовая ситуация: Ввод отрицательного числа
Исходные данные: -9
Ожидаемый результат: Некорректные данные.
Полученный результат:
Рисунок 8—Тест 2.1
Тест 2.2
Тестовая ситуация: Ошибка ввода
Исходные данные: 1o
Ожидаемый результат: Некорректные данные.
Полученный результат:
Рисунок 9—Тест 2.2
[1] При N>10 программа работает больше двух минут