Пилипчук О.П., вчитель інформатики Гаврилівської ЗОШ Теофіпольського району Хмельницької області
Задача про розстановку знаків
Рекурсія у Паскалі (FreePascal)
У навчальному посібнику для 3 класу (Т.Ф.Баєва Дізнайся. Відгадай. Попробуй) вміщена така
Задача
Напиши підряд 7 цифр 1234567. З'єднай їх знаками додавання і віднімання так, щоб в сумі вийшло 40.
Після того, як нашвидкоруч не вдалося відшукати розв'язок, виникла ідея написати програму. Ручну працю - на плечі комп'ютера!
Базовий матеріал
- Рядковий тип даних.
- Множинний тип даних.
- Процедури користувача.
- Рекурсія. Рекурсивні процедури.
- Область видимості змінних. Локальні та глобальні змінні.
Розробка програми
Якщо з подальшого тексту вилучити пояснення, залишиться працездатна програма (жодних гарантій! :)
program rebus;
1. Спочатку - структура даних... Доволі примітивна :) Рядкова змінна s для формування розв'язку - і все:
var s:string;
2. А тут вже цікавіше! При переборі варіантів стане в нагоді функція для обчислення значення виразу, записаного в рядку s. Наприклад, виявивши в рядку такі дані: "12+3+4-5+67" функція поверне ціле число 81. Оскільки змінна s - глобальна, то немає потреби передавати її в якості аргументу. Це трохи прискорить роботу комп'ютера:
function res:integer;
var i,sum,d:integer;
op:char;
begin
2. У змінній sum нагромаджуватиметься значення виразу:
sum:=0;
3. У змінній d формуватиметься значення чергового числа:
d:=0;
4. Змінна op повинна містити знак операції, яка буде виконана над sum і сформованим числом d:
op:='+';
5. Власне обчислення робиться в процесі посимвольного аналізу рядка:
for i:=1 to length(s) do
6. Якщо наступний символ - цифра - вона дописується до числа, яке містить змінна d:
if s[i] in ['1'..'7'] then d:=d*10+ord(s[i])-ord('0')
7. В іншому випадку, тобто при появі в рядку знака, залежно від знака операції, збереженого в змінній op буде виконане додавання або віднімання:
else begin case op of
'+': sum:=sum+d;
'-': sum:=sum-d;
end;
8. ... після чого змінна d буде звільнена для формування наступного доданка:
d:=0;
9. ... а в змінну op буде скопійований з рядка знак наступної операції:
op:=s[i]
end;
10. Цикл завершено. Але, оскільки коректний рядок завершується цифрою, а операція виконувалась тільки при знаходженні знака, щоб не втратити останнє число, слід ще раз виконати операцію:
case op of
'+': sum:=sum+d;
'-': sum:=sum-d;
end;
11. Значення виразу готове. Передаємо його на місце виклику функції:
res:=sum;
end;
12. Тепер можна скласти рекурсивну процедуру для перебору різних варіантів розміщення знаків "+" та "-" між цифрами. Вхідним аргументом буде чергова цифра, ще не приєднана до рядка:
procedure rec(n:char);
begin
13. Таким чином, спроба приєднати цифру 8 означає, що рядок сформований, і можна перевірити, чи його значення не дорівнює 40. Якщо це так - виведемо рядок на екран:
if (n='8') then begin if res=40 then writeln(s) end
else begin
14. В іншому разі, якщо рядок непорожній і закінчується не знаком...
if (length(s)>0) then
if (s[length(s)]<>'+') and (s[length(s)]<>'-') then begin
15. ... - приєднуємо до нього знак "+" і робимо рекурсивний виклик процедури, передаючи їй той самий символ:
s:=s+'+'; rec(n);
16. Після повернення - видаляємо останній символ, тобто, знак "+", і виконуємо такі ж дії зі знаком "-":
delete(s,length(s),1);
s:=s+'-'; rec(n); delete(s,length(s),1);
end;
17. Нарешті, пробуємо безпосередньо приєднати отриману цифру до рядка, а в рекурсивному виклику передаємо вже наступну цифру. Після повернення теж видаляємо останній символ:
s:=s+n; rec(succ(n));
delete(s,length(s),1);
end
end;
18. А ось і програма... Щось її погано видно - маленька вона якась :) Дійсно, залишилось створити порожній рядок і звернутися до описаної вище процедури, передавши їй першу з цифр - одиницю:
begin
s:='';
rec('1')
end.
Підсумок
Отримане виведення перевершило всі сподівання:
1-2-3+45+6-7
12+34-5+6-7
12-34-5+67
Задача має три розв'язки!
Але кожен третьокласник скаже вам, що два з них... - "неправильні". Адже при обчисленні першого і третього значень в якийсь момент доводиться віднімати від меншого числа більше. А від'ємні числа вивчають значно пізніше...
Интернет реклама
