Логическая рекурсия. Любые языки, но желательно pascal.

[ИльяБлум]

Задача с до боли простым и баянистым условием.
За один ход с числом делается такая операция: если число не делится на 3,то вычитаем 1, а если делится, то собсно делим. Из 39 единица получается за 5(это n) таких ходов.
Сколько натуральных чисел, каждое из которых превращается в единицу за n ходов? (0<=n<=35)
@Получить n
@Вывести кол-во
К примеру в пятерке 20 чисел.
Можно на c++, pascal, java. Можно и на русском просто алгоритм обьяснить или суть процессии.

[Serge_Bliznykov]

К примеру в пятерке 20 чисел.

что это означает?? в какой "пятерке" ?!


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

function FindNum(k: int64; n, nFind: byte) : integer;
begin
  Result := 0;
  if n=nFind then begin
    Result := 1;
    Exit;
  end;
  Result := Result + FindNum(k*3, n+1, nFind);
  Result := Result + FindNum(k+1, n+1, nFind);
end;

[Аватар]

Серж, не врубаюсь как к ней обратиться, чтобы в цикле вычислить для n от 1 до 35? Хочу свой вариант проверить

function CalcCount(n: Integer): Integer;
var i,j,k: Integer;
    a: array[0..4] of Integer;
begin
  a[0]:=0;
  a[1]:=2;
  a[2]:=3;
  a[3]:=6;
  a[4]:=11;
  if n<5 then CalcCount:=a[n]
  else begin
    for i:=5 to n do begin
      k:=a[4]*2-a[1];
      for j:=1 to 3 do a[j]:=a[j+1];
      a[4]:=k;
    end;
    CalcCount:=a[4];
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,j: Integer;
begin
  for i:=0 to 35 do begin
    j:=CalcCount(i);
    Memo1.Lines.Add(Format('%d   %d',[i,j]));
  end;
end;

[Serge_Bliznykov]

Сообщение от Аватар

Серж, не врубаюсь как к ней обратиться, чтобы в цикле вычислить для n от 1 до 35? Хочу свой вариант проверить

дык.
третьим параметром задаётся количество шагов.

например, если нужно найти количество чисел с шагом n=3
то пишем:

Find := 3;
allcount := FindNum(1, 0, Find);

p.s. количество вариантов с увеличением n растёт очень сильно.
Не уверен, что вычисление для больших n уложится в разумные рамки!

[Аватар]

Так, что ли? Степени двойки считает и очень долго

  for i:=1 to 35 do begin
    j := FindNum(1, 0, i);
    Memo1.Lines.Add(Format('%d   %d',[i,j]));
  end;

У меня для 35 - 1748130326

0   0
1   2
2   3
3   6
4   11
5   20
6   37
7   68
8   125
9   230
10   423
11   778
12   1431
13   2632
14   4841
15   8904
16   16377
17   30122
18   55403
19   101902
20   187427
21   344732
22   634061
23   1166220
24   2145013
25   3945294
26   7256527
27   13346834
28   24548655
29   45152016
30   83047505
31   152748176
32   280947697
33   516743378
34   950439251
35   1748130326

[Serge_Bliznykov]

Так, что ли? Степени двойки считает и очень долго

ага. Дык, может это и есть решение - просто выдать степень двойки?!

У меня для 35 - 1748130326

0   0
1   2
2   3
....

а можно поинтересовать, что это за цифры?
слева число шагов, справа - количество чисел, которые за это число шагов можно привести к единице?

я неправильно понял задачу?
число шагов = 0, только одно число за 0 шагов можно привести к единице - это число 1

число шагов = 1
число подходящих чисел - 2 (это числа 2 и 3)
3 steps 3/3 => =1
2 steps 2-1 => =1

число шагов = 2
число подходящих чисел - 4 (это числа 9,4,6,3)
9 steps 9/3 => 3/3 => =1
4 steps 4-1 => 3/3 => =1
6 steps 6/3 => 2-1 => =1
3 steps 3-1 => 2-1 => =1

и т.д.

где я ошибаюсь?!

ДОБАВЛЕНО.
Ага, вижу, где я ошибаюсь. число 3 не подходит, из него нельзя отнимать едиицу, т.к. оно кратно 3!!

в принципе, такой код работает:

function FindNum(k: int64; n, nFind: byte) : integer;
begin
  Result := 0;
  if n=nFind then begin
    Result := 1;
    Exit;
  end;
  Result := Result + FindNum(k*3, n+1, nFind);
  if ((k+1) mod 3)<>0 then
     Result := Result + FindNum(k+1, n+1, nFind);
end;

хотя, конечно, после кода (с) Аватар в этом коде смысла нет.

[Аватар]

слева число шагов, справа - количество чисел, которые за это число шагов можно привести к единице?

Ага.

Я сначала пришел к тому, что если в троичном исчислении сложить все цифры числа в нашей родненькой десятичной и прибавить количество значащих цифр, то результат без двойки и будет количеством шагов, за которые к 1 приходит
20011 -> 2+1+1+5=9 -> 7 шагов
Попытался с помощью числа сочетаний все посчитать, но кучу малу получил. А потом созрел до рекурсии K(i)=2*K(i-1)+K(i-4) для i>4

[Serge_Bliznykov]

Аватар, круто!

А я не смог разобраться в вашем решении...
Видимо, оно выше моего понимания!

[Аватар]

Я сам уже запутался, завтра на свежую голову изложу ход мыслей

[ИльяБлум]

Первый раз на вашем форуме. Абсолютно все решение понял. Еще раз большое спасибо.
У меня получилось слегка аналогичное решение с аватаром... единственное, я не до конца додумался. Очень странно (как тяжелый наркоман) начал решать, а когда ответы на более высокие n не совпали (у меня был ответ на n=12,30; ), начал придумывать какие-то b и ее рекурсии...
Вообщем самую страшную версию не выложу, но если вы хотите улыбнуться над школьником, то можете глянуть эту.

var
a,b:array[1..3] of integer;
k,i:integer;
begin
readln(k);
a[1]:=3;
a[2]:=6;
b[1]:=0;
b[2]:=0;
for i:=4 to k do
begin
  if i=10 then b[1]:=1;
  if i=13 then b[2]:=2;
  a[3]:=2*a[2] - round((Trunc(a[1]/4) + trunc(a[1]/3) + 1)/2)-b[1] ;
  a[1]:=a[2];
  a[2]:=a[3];
  if i>12 then begin
  b[3]:=2*b[2] - trunc(b[1]/3);
  b[1]:=b[2];
  b[2]:=b[3];end;
end;
writeln(a[2]);
end.