Помощь - Поиск - Пользователи - Календарь
Полная версия: рекурсия
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
marwell
Определить число, получаемое выписыванием в обратном порядке цифр заданного натурального числа (использовать рекурсивную функцию). Ничего не приходит в голову blink.gif Кто-нибудь, дайте пожалуйста направление(код постараюсь написать сам)
Client
брать остатока от деления на 10, делай с ним что надо, и дели число на 10. Так пока число не будет равно 0.
marwell
Цитата(Client @ 2.04.2010 16:21) *

брать остатока от деления на 10, делай с ним что надо, и дели число на 10. Так пока число не будет равно 0.

ааа, точно! как я не догадался? спасибо большое smile.gif
marwell
черт, даже не знаю, как это можно написать с рекурсией sad.gif ведь после операции mod 10 мы потеряем все остальные числа
volvo
Цитата
ведь после операции mod 10 мы потеряем все остальные числа
Ничего не потеряем:
procedure rec(x: longint);
begin
if x > 0 then
begin
write(x mod 10);
rec(x div 10);
end;
end;
marwell
спасибо! good.gif
marwell
а реально ли сделать это через функцию, а не процедуру?
Client
пол часа мучений стоили этого smile.gif
скорей всего можно и по другому.
вот что получилось
uses crt;
var
a,b:integer;

function asd(x,i:integer) :integer;
begin
if x=0 then asd:=-b
else begin
if x div 10 <>0 then
b:=b +i*10+ x mod 10;
asd:=(i*10+ x mod 10) + asd(x div 10,i*10+ x mod 10 )
end;
end;

begin
clrscr;
b:=0;
readln(a);
writeln(asd(a,0));
readkey
end.
volvo
Цитата
скорей всего можно и по другому.
Можно конечно... Заметь, без побочных эффектов. Старайся вообще обходиться без них. А уж об использовании глобальных переменных я вообще не хочу вспоминать smile.gif

function r(x: longint): longint;
const b: longint = 0;
begin
if x = 0 then begin
r := 0; b := 1;
end
else begin
r := r(x div 10) + b * (x mod 10); b := 10 * b;
end;
end;

begin
writeln(r(12345));
end.
marwell
спасибо огроменное good.gif
marwell
Цитата(volvo @ 2.04.2010 23:13) *

Можно конечно... Заметь, без побочных эффектов. Старайся вообще обходиться без них. А уж об использовании глобальных переменных я вообще не хочу вспоминать smile.gif

function r(x: longint): longint;
const b: longint = 0;
begin
if x = 0 then begin
r := 0; b := 1;
end
else begin
r := r(x div 10) + b * (x mod 10); b := 10 * b;
end;
end;

begin
writeln(r(12345));
end.


 const b: longint = 0;
begin
if x = 0 then begin
r := 0; b := 1;
а разве можно константе b=0 присвоить значение b:=1?
Lapp
Цитата(marwell @ 3.04.2010 10:23) *
а разве можно константе b=0 присвоить значение b:=1?
Типизированной константе - можно. По сути, это просто инициализированные переменные. Неудачное название им дали в Борланде..
marwell
программа выдает только нули blink.gif
Lapp
Цитата(marwell @ 3.04.2010 10:38) *
программа выдает только нули blink.gif

Попробуй вот так:
function r(x: longint): longint;
var
a,b,c,d: longint;
begin
if x = 0 then
r := 0
else begin
b:= 1;
while x div b div 10 > 0 do b:=b*10;
a:= x div b;
c:= x-a*b;
d:= 1;
while c div d div 10 > 0 do d:=d*10;
r := a + b div d*r(c );
end;
end;

begin
writeln(r(12345));
end.

Тут наверняка наворочено больше, чем нужно, и не очень красиво ))..
Client
хм, а собственно где нули получаются? при каких данных?
marwell
Цитата(Client @ 3.04.2010 10:55) *

хм, а собственно где нули получаются? при каких данных?

с твоим-то кодом все работает))
Client
volvo good.gif есть над чем подумать smile.gif

Добавлено через 2 мин.
код volvo рабочий. Что не так?
volvo
Цитата(Client)
Что не так?
Не так работает под Турбо-Паскалем, надо разбивать вычисление выражения на 2 этапа:
function r(x: longint): longint;
const
b: longint = 0;
var v: longint;
begin
if x = 0 then begin
r := 0; b := 1;
end
else begin
v := r(x div 10); { <--- Первый этап }
r := v + b * (x mod 10); b := 10 * b; { <--- Второй этап }
end;
end;

begin
writeln(r(1234543));
end.
Вот теперь будет работать одинаково под любым компилятором.
Lapp
Цитата(volvo @ 3.04.2010 12:50) *
Не так работает под Турбо-Паскалем
У меня не каждый раз срабатывала под FPC.. Сейчас воспроизвести не могу.
Не знаю, стоит ли полагаться на такие вещи..
volvo
Цитата
стоит ли полагаться на такие вещи..
На какие такие? Я не делаю ничего запрещенного, заметь, сначала - рекурсивный вызов, потом - использование значения b. То есть, никогда не будет использовано неинициализированное тобой значение b. Чтобы оно начало использоваться - рекурсия должна дойти до конца (x = 0), но тогда b уже станет равно 1. Опять же, "типизированная константа" = "статическая переменная", она описывается в сегменте данных (а не в стеке, как обычная переменная), и поэтому сохраняет свое значение не только между вызовами простых функций, но и между вызовами рекурсивных тоже, так что и с этой стороны подвохов быть не может. Так что это вполне приемлемая конструкция.

Цитата
У меня не каждый раз срабатывала под FPC
Если еще у кого-то будут неправильные срабатывания - отпишитесь здесь, интересно, на каких значениях это происходит. Чему разно изначальное число, и что возвращает функция. Единственный вариант, который приходит в голову - это когда "перевернутое" число не влезет в LongInt (например, 1234567899), но тут уж ничего не поделаешь.
Lapp
Цитата(volvo @ 3.04.2010 14:10) *
На какие такие? Я не делаю ничего запрещенного,
Я все это понимаю, потому я и выразился туманно smile.gif.
Способ, конечно, аппетитный. Чтобы корректно обрабатывать внутренние нули мне пришлось оценивать порядок частного, вводить дополнительный цикл - а тут все уитывается на автомате. Вроде действительно должно работать.. Я наблюдал ошибку на ноутбуке, а тут (на домашнем компе) не могу воспроизвести. Завтра попробую еще на ноуте.

Не исключено, что я что-то путаю. Значения были 12345 и 67890, кажется.
Lapp
Цитата(Lapp @ 3.04.2010 14:46) *
наблюдал ошибку на ноутбуке, а тут (на домашнем компе) не могу воспроизвести. Завтра попробую еще на ноуте.

Не исключено, что я что-то путаю.
Сейчас пытался снова получить ошибку на ноуте (FPC 2.2.4, Vista 32) - не выходит. Сильно подозреваю, что это я накосячил. К сожалению, то окно я закрыл, и псомотреть нет возможности. С извинениями беру свои слова обратно )).

На всяк случай спрошу: marwell, а ты можешь привести точный вариант проги, где у тебя получаются нули? Спасибо.

Я никогда не использовал статическую переменную через константу в процедуре. Может, оно и лучше, поскольку она получается объявленной прямо тут, а не где-то там. Но все же смысл ее как и у глобальной. И это значит, в частности, что нельзя вызывать такую процедуру параллельно.. Но если это не подразумевается, то все ОК. Запомним это )), спасибо.
volvo
Цитата
а ты можешь привести точный вариант проги, где у тебя получаются нули?
Нули получаются при запуске программы из 9-го поста (без добавленного позже разбиения на 2 этапа) под Турбо-Паскалем. Причины, кстати, я до сих пор не понимаю, Не хочет вычислять выражение, заданное вот так:
    r := r(x div 10) + b * (x mod 10); b := 10 * b;

А если поменять слагаемые местами:
    r := b * (x mod 10) + r(x div 10); b := 10 * b;

, то все становится прекрасно и удивительно - теперь Дедушка Турбо соизволил посчитать выражение правильно. Но тогда FPC напрочь отказывается возвращать правильный результат blink.gif Замкнутый круг какой-то... С чем это может быть связано - не знаю. Скорее всего что-то связанное с Порядком вычисления выражений. Так что лучше, действительно, разбить выражение на 2 части, используя промежуточную переменную (см. пост №18)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.