Задача: Лестница

Yuri V · Регистрация: 25.05.2022

Author24 — интернет-сервис помощи студентам

Имеется рабочая программа на "старом" Паскале, которая рекурсивно находит количество вариантов прохождения заданной лестницы с вариантом шага на 1, 2 или 4 ступени.

Pascal

var
  всего: longint;
  ступени: integer;
 
procedure шаг(ход: integer);
begin
  if ход - 1 = 0 then inc(всего) //последний 1 шаг
  else
  if ход > 0 then
  begin
    if (ход - 2) = 0 then inc(всего)  //последний 2 шаг
         else
    if (ход - 2 > 0) then шаг(ход - 2);
    
    if (ход - 4) = 0 then inc(всего)  //последний 4 шаг
          else 
    if (ход - 4) > 0 then шаг(ход - 4);  
  end;
end;
 
begin
  всего := 0;
  write('Длина лестницы= ');
  readln(ступени);
  шаг(ступени);
  writeln('Всего вариантов: ', всего);
end.

Однако теперь нужно показать допустимые варианты.
Я посоветовал PascalABC.NET, и учитель вроде не возражает.

@JuriiMW · 05.06.2022, 09:56

Сообщение от Yuri V

Имеется рабочая программа на "старом" Паскале

А вы именно эту программу не пробовали запускать „на "старом" Паскале“?

Сообщение от Yuri V

Я посоветовал PascalABC.NET

Ну, так-так!
С этого места поподробнее…
Т.е. вы посоветовали,
а делать должны мы?

@Sun Serega · 05.06.2022, 09:57

Перепишите оригинальное задание, этот код выглядит как очень страшное усложенение простейшей логики. Должны быть достаточно case с 5 вариантами.

Yuri V · 05.06.2022, 11:24 **[ТС]**

JuriiMW, а если чуть подумать над значением фразы рабочая, т.е. принятая учителем программа? Да никто не заставляет: есть что подсказать по выводу рекурсии или структуры в целом - хорошо, нет - тоже нормально, но не тратьте буквы, дышите. Хотя точнее указывать "в стиле или духе старого Паскаля", но по коду и ежу понятно.

А лично мне пока ничего особо в голову пока не приходит, потому что если делать по старинке - показывает странный вывод (см. ниже).

Sun Serega, логика прямо в процедуре: cколько вариантов можно сделать по 2 или 4 шага чтобы пройти заданную лестницу, при необходимости делая последний шаг для нечётных?
Вариант с таким выводом-

Pascal

procedure шаг(ход: integer);
begin
  if ход - 1 = 0 then begin writeln(1);inc(всего)end //последний 1 шаг
  else
  if ход > 0 then begin
    if (ход - 2) = 0 then begin writeln(2);inc(всего)end  //последний 2 шаг
         else
    if (ход - 2 > 0) then begin Write(2);шаг(ход - 2)end;
    
    if (ход - 4) = 0 then begin writeln(4);inc(всего)end  //последний 4 шаг
          else 
    if (ход - 4) > 0 then begin Write(4);шаг(ход - 4)end;  
  end;//IF
end;

как-то не так, потому что

Длина лестницы= 6
222 +
4 <---- что это такое? Почему пропускает единицы?
42 +
Всего вариантов: 3

Задача не моя, не я её делал, но засчитана как правильная, а как появится лицеист - уточню.

Добавлено через 2 минуты
Хотя без контрольных примеров не исключена безалаберность как учителя, так и исполнителя.

@Sun Serega · 05.06.2022, 11:29

Сообщение от Yuri V

пропускает единицы?

А каким образом должна получится еденица, при отнимании чётных (2 и 4) от чётного (6)?

Добавлено через 1 минуту
Ну в любом случае, таки ждём задание.

ФедосеевПавел · 05.06.2022, 12:56

Переменная "ход" имеет какой-то физический смысл?
Потому, что в процедуре всего одна переменная и три константы (величины шага) - 1, 2 и 4.

Yuri V · 05.06.2022, 14:03 **[ТС]**

ФедосеевПавел, логично, это обычная рекурсия с вариантами ходов.
Проще говоря, нужно "2"-ками и "4"-ками набрать заданную сумму, при необходимости дополнив "1", но условие уточню.

Меня больше интересует почему процедура засчитывает неполные варианты как с "4" выше.
Вполне возможно, что Sun Serega прав и я перепутал выход из частичной рекурсии за полный ответ (всю цепочку).

Кликните здесь для просмотра всего текста

Pascal

procedure шаг(ход: integer);
begin
  write('[',ход,']');
  if ход - 1 = 0 then begin writeln(1);inc(всего)end //последний 1 шаг
  else
  if ход > 0 then begin
    if (ход - 2) = 0 then begin writeln(2);inc(всего)end  //последний 2 шаг
         else
    if (ход - 2 > 0) then begin Write(2);шаг(ход - 2)end;
    
    if (ход - 4) = 0 then begin writeln(4);inc(всего)end  //последний 4 шаг
          else 
    if (ход - 4) > 0 then begin Write(4);шаг(ход - 4)end;  
  end;//IF
end;

Длина лестницы= 6
[6]2[4]2[2]2
4
4[2]2
Всего вариантов: 3

ФедосеевПавел · 05.06.2022, 16:48

Переменная "ход" - это номер текущей ступени лестницы.

Если сделать стек (хоть на существующих типах, хоть на массиве), в который заносить номера ступеней (переменные "шаг"), то после того, как будет получено условие "шаг"=0 (if ход - 1 = 0) и опустошать на один элемент перед выходом из подпрограммы, то из этого стека можно вывести все номера ступеней лестницы, через которые проходит данное полученное решение.

@JuriiMW · 05.06.2022, 17:10

Вообще — это задание на динамическое программирование.
Здесь просто нужен линейный массив.

ФедосеевПавел · 05.06.2022, 19:51

Если речь о подсчёте количества вариантов решения.
Но преподаватель усложнил задание

Сообщение от Yuri V

Однако теперь нужно показать допустимые варианты.

Добавлено через 2 часа 4 минуты
У меня нет PABC.NET, но и на FPC алгоритм ясен.
Для N=6 получаю количество вариантов прохождения лестницы не 3, а 18.[PASCAL]

Pascal

program test;
 
var
  Path: array of integer;
  Len:  integer;
 
  procedure ShowPath;
  var
    i: integer;
  begin
    for i := 0 to Len - 1 do
      Write(Path[i], ' ');
    writeln;
  end;
 
  function Step(N: integer): integer;
  begin
    if N = 0 then
    begin
      ShowPath;
      Step := 1;
      exit;
    end;
    Path[Len] := N;
    Inc(Len);
    Step:=0;
    if N >= 1 then
      Step := Step + Step(N - 1);
    if N >= 2 then
      Step := Step + Step(N - 2);
    if N >= 4 then
      Step := Step + Step(N - 4);
    Dec(Len);
  end;
 
var
  N: integer;
  Count: integer;
begin
  N := 6;
  SetLength(Path, N);
  Count := Step(N);
  writeln('Count ', Count);
end.

Добавлено через 3 минуты
В коде из сообщения #1 ошибка - не рассматривается вариант перехода на ступень +1

@mr-Crocodile · 06.06.2022, 09:49

Сообщение от ФедосеевПавел

У меня нет PABC.NET, но и на FPC алгоритм ясен.

на PascalABC.NET ваш вариант можно записать так:

Pascal

program test;
 
var
  Path: array of integer;
  Len:  integer;
 
  procedure ShowPath;
  var
    i: integer;
  begin
    for i := 0 to Len - 1 do
      Write(Path[i], ' ');
    writeln;
  end;
 
  function Step(N: integer): integer;
  begin
    if N = 0 then
    begin
      ShowPath;
      Step := 1;
      exit;
    end;
    Path[Len] := N;
    Inc(Len);
    result:=0;
    if N >= 1 then
      result := result + Step(N - 1);
    if N >= 2 then
      result := result + Step(N - 2);
    if N >= 4 then
      result := result + Step(N - 4);
    Dec(Len);
  end;
 
var
  N: integer;
  Count: integer;
begin
  N := 6;
  SetLength(Path, N);
  Count := Step(N);
  writeln('Count ', Count);
end.

ну, или так:

Pascal

var
  Path: array of integer;
  Len:  integer;
 
  function Step(N: integer): integer;
  begin
    if N = 0 then
    begin
      Path[0:len].Println;
      Step := 1;
      exit;
    end;
    Path[Len] := N;
    Inc(Len);
    result:=0;
    if N >= 1 then
      result := result + Step(N - 1);
    if N >= 2 then
      result := result + Step(N - 2);
    if N >= 4 then
      result := result + Step(N - 4);
    Dec(Len);
  end;
 
begin
  var N := 6;
  SetLength(Path, N);
  writeln('Count ', Step(N));
end.

@JuriiMW 5077 / 2649 / 2349 Регистрация: 10.12.2014 Сообщений: 10,024
	05.06.2022, 09:56	2
	Сообщение от Yuri V Имеется рабочая программа на "старом" Паскале А вы именно эту программу не пробовали запускать „на "старом" Паскале“? Сообщение от Yuri V Я посоветовал PascalABC.NET Ну, так-так! С этого места поподробнее… Т.е. вы посоветовали, а делать должны мы? 0

@Sun Serega 2300 / 1413 / 514 Регистрация: 07.04.2017 Сообщений: 4,713
	05.06.2022, 09:57	3
	Перепишите оригинальное задание, этот код выглядит как очень страшное усложенение простейшей логики. Должны быть достаточно `case` с 5 вариантами. 0

@Sun Serega 2300 / 1413 / 514 Регистрация: 07.04.2017 Сообщений: 4,713
	05.06.2022, 11:29	5
	Сообщение от Yuri V пропускает единицы? А каким образом должна получится еденица, при отнимании чётных (2 и 4) от чётного (6)? Добавлено через 1 минуту Ну в любом случае, таки ждём задание. 0

ФедосеевПавел Модератор 8475 / 4334 / 1642 Регистрация: 01.02.2015 Сообщений: 13,455 Записей в блоге: 8
	05.06.2022, 12:56	6
	Переменная "ход" имеет какой-то физический смысл? Потому, что в процедуре всего одна переменная и три константы (величины шага) - 1, 2 и 4. 0

ФедосеевПавел Модератор 8475 / 4334 / 1642 Регистрация: 01.02.2015 Сообщений: 13,455 Записей в блоге: 8
	05.06.2022, 16:48	8
	Переменная "ход" - это номер текущей ступени лестницы. Если сделать стек (хоть на существующих типах, хоть на массиве), в который заносить номера ступеней (переменные "шаг"), то после того, как будет получено условие "шаг"=0 (`if ход - 1 = 0`) и опустошать на один элемент перед выходом из подпрограммы, то из этого стека можно вывести все номера ступеней лестницы, через которые проходит данное полученное решение. 1

@JuriiMW 5077 / 2649 / 2349 Регистрация: 10.12.2014 Сообщений: 10,024
	05.06.2022, 17:10	9
	Вообще — это задание на динамическое программирование. Здесь просто нужен линейный массив. 0

	06.06.2022, 09:49

Опции темы

Задача: Лестница

Решение