Вівторок, 12.12.2017
Творча лабораторія

Навчальні посібники та робочі зошити з інформатики - якісно і дешево


Меню сайту
Реклама
Категорії каталогу
MS Visual C++ 2005 Express Edition [3]
Середовища програмування [7]
Особливості встановлення та використання різних середовищ програмування
MS Visual Basic 6 [1]
Microsoft Visual Basic
C# [7]
Програмування мовою C#
C++ [3]
Паскаль [4]
ЛОГО [1]
Олімпіадне програмування [0]
Головна » Статті » Програмування » Паскаль

Задача про розстановку знаків. Рекурсія у Паскалі

Нові статті

[17.09.2015] [Інформація]
Інформатика — місток між предметами
[20.05.2015] [Інформація]
Алгоритми і виконавці: безкомп’ютерний етап
[12.04.2015] [Навчальні посібники]
Авторська концепція комплекту «Інформатика. Базовий курс. 7 клас»

Пилипчук О.П., вчитель інформатики Гаврилівської ЗОШ Теофіпольського району Хмельницької області

Задача про розстановку знаків

Рекурсія у Паскалі (FreePascal)

У навчальному посібнику для 3 класу (Т.Ф.Баєва Дізнайся. Відгадай. Попробуй) вміщена така

Задача

Напиши підряд 7 цифр 1234567. З'єднай їх знаками додавання і віднімання так, щоб в сумі вийшло 40.

Після того, як нашвидкоруч не вдалося відшукати розв'язок, виникла ідея написати програму. Ручну працю - на плечі комп'ютера!

Базовий матеріал

  1. Рядковий тип даних.
  2. Множинний тип даних.
  3. Процедури користувача.
  4. Рекурсія. Рекурсивні процедури.
  5. Область видимості змінних. Локальні та глобальні змінні.

Розробка програми

Якщо з подальшого тексту вилучити пояснення, залишиться працездатна програма (жодних гарантій! :)

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


Задача має три розв'язки!

Але кожен третьокласник скаже вам, що два з них... - "неправильні". Адже при обчисленні першого і третього значень в якийсь момент доводиться віднімати від меншого числа більше. А від'ємні числа вивчають значно пізніше...

 

 


Интернет реклама
Категорія: Паскаль | Додав: teachlab (10.04.2009)
Переглядів: 2561 | Комментарі: 1 | Рейтинг: 0.0/0
Всього коментарів: 1
1  
Спасибо, пригодилось. Даю рекурсию в профильном классе.

Додавати коментарі можуть тільки зареєстровані користувачі.
[ Реєстрація | Вхід ]
Форма входу
Пошук
Друзі сайту

Підтримка
Ви можете підтримати цей проект:

WMR164778923006
WMZ277001591405

Система Orphus

Маєте свій сайт?
Заробіть на ньому грошей!


Не маєте власного сайту?
Заробіть на обміні файлами!
Статистика
Copyright Пилипчук О.П. © 2017
div id=