Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.11.2017, 11:02   #1
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию Сломанные ступеньки

Всем привет. Помогите доработать задачу.

Заяц может ходить на следующую ступеньку, переступать через одну и через две, однако некоторые ступеньки сломаны. Сколькими способами можно попасть на N-ю ступеньку.

входные данные
В первой строке записано число N - номер ступеньки на которую нужно попасть и K - количество сломанных ступеней. (1 ≤ k ≤ n ≤ 60). В следующей строке записаны номера ступеней которые сломаны.

Исходные данные
Вывести одно число, количество способов которыми можно попасть на строчку с номером N, или -1, если попасть невозможно.

Вот мой код вроде на Паскале работает, а на сайте проходит на 20%.
Суть идеии: если количество сломанных ступенек больше 2 и j+1 элемент находится между j и j+2 элементами (3 сломанные ступеньки идут подряд) то -1 иначе результат.

Код:
var k,kp,n,i: byte;
a,b,c,q,j: int64;
a1:array[-999..999] of longint;
p:boolean;
begin
  read(n);
  read(k);
  for j:=1 to k do
  begin
   read (a1[j]);
  end;
  kp:=0;
  for j:=1 to k do
  begin
    kp:=kp+1;
  end;
  for j:=1 to k do
  begin
    if (kp>2) and (a1[j+1]=a1[j]+1)and (a1[j+1]=a1[j+2]-1) then p:=true;
  end;
  begin
    n:=n-k;
    a:=1 ;
    b:=2 ;
    c:=4 ;
    case n of
    1: q:=1;
    2: q:=2;
    3: q:=4;
    end;
    for i:=n downto 4 do
    begin
      q:=a+b+c;
      a:=b; b:=c; c:=q
   end;
   if p then writeln ('-1') else
   writeln(q);
  end;
end.
_____
Код программы нужно выделять (форматировать) тегами [CODE] (читать FAQ)
Модератор

Последний раз редактировалось Serge_Bliznykov; 07.11.2017 в 11:31.
kim-im вне форума Ответить с цитированием
Старый 08.11.2017, 07:56   #2
NetSpace
Участник клуба
 
Аватар для NetSpace
 
Регистрация: 03.06.2009
Сообщений: 1,792
По умолчанию

комбинаторика, что ли?
С из N по K надо считать?
а есть проверка, что сломанных ступенек K Больше или равно, чем N? - тогда попасть на последнюю ступеньку нельзя и должно выводить -1. а если последняя ступенька цела (есть хоть одна целая), то уже есть один способ туда добраться - перепрыгнуть через все сломанные ступеньки сразу на последнюю.
и для чего в этом коде цифры?
Код:
a:=1 ;
    b:=2 ;
    c:=4 ;
    case n of
    1: q:=1;
    2: q:=2;
    3: q:=4;
Программирование - это единственный способ заставить компьютер делать то, что тебе хочется, а не то, что приходится.

Последний раз редактировалось NetSpace; 08.11.2017 в 08:01.
NetSpace вне форума Ответить с цитированием
Старый 08.11.2017, 10:17   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Для начала нужно найти решение как попасть с 1-ой на последнюю ступеньку участка без поломанных ступенек. И найти для этого количество решений линейного диофантового уравнения x+2y+3z=n-1, где n количество ступенек. А дальше слева направо участок за участком с учетом того, что начало и конец этого участка зависит от количества поломанных ступенек в начале и в конце участка. И само собой, если где-то подряд больше 2-ух поломанных то нет решения
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 08.11.2017, 10:54   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

задача известная, на динамическое программирование.
на форуме была http://www.programmersforum.ru/showthread.php?t=168384
(без сломанных ступенек, но зато заяц мог прыгать на K ступенек).

как эту со сломанными решать я не знаю, но думаю, что нужно в том же направлении двигаться - заполнять массив [1..N] значениями функции F(X), которое означает, сколькими способами можно попасть на ячейку со значением X, но с учётом сломанных ступенек.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 09.11.2017, 12:58   #5
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от NetSpace Посмотреть сообщение
комбинаторика, что ли?
С из N по K надо считать?
а есть проверка, что сломанных ступенек K Больше или равно, чем N? - тогда попасть на последнюю ступеньку нельзя и должно выводить -1. а если последняя ступенька цела (есть хоть одна целая), то уже есть один способ туда добраться - перепрыгнуть через все сломанные ступеньки сразу на последнюю.
и для чего в этом коде цифры?
Код:
a:=1 ;
    b:=2 ;
    c:=4 ;
    case n of
    1: q:=1;
    2: q:=2;
    3: q:=4;
Цифры для динамики.
Задача работает для целых ступенек. Я добавил код для сломанных, но где-то он не работает верно.
Прошу помочь
kim-im вне форума Ответить с цитированием
Старый 09.11.2017, 14:20   #6
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Короче, Вы сами в своём коде не можете разобраться, а хотите чего-то от нас..
Лично мне проще с нуля написать..
Код:
a:=0; b:=0; c:=1;
for i:=1 to n do begin
  d:= a+b+c;
  if <i-я ступенька битая> then d:=0;
  a:=b; b:=c; c:=d;
end;
print(c);
Black Fregat вне форума Ответить с цитированием
Старый 09.11.2017, 14:43   #7
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Лично мне проще с нуля написать..
Гениально!!!! Гонял ваш код. Всё работает!

Единственно, нужно ноль (если ноль вариантов) преобразовать в -1,
но это несущественная мелочь.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 10.11.2017, 09:31   #8
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Ещё можно остановить цикл, если все три уйдут в ноль
Black Fregat вне форума Ответить с цитированием
Старый 10.11.2017, 09:45   #9
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Ещё можно остановить цикл, если все три уйдут в ноль
в данной задаче ограничение на n <= 60
цикл прервать, конечно, можно, но чисто красоты ради. На быстродействие это заметного влияния не окажет.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 10.11.2017, 11:03   #10
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от Black Fregat Посмотреть сообщение
Короче, Вы сами в своём коде не можете разобраться, а хотите чего-то от нас..
В коде я разбираюсь:
Код:
var n,i: byte;
a,b,c,q: uint64;
begin
readln(n);
if n=0 then q:=0 else
a:=1 ;
b:=2 ;
c:=4 ;
case n of
1: q:=1;
2: q:=2;
3: q:=4
else
for i:=n downto 4 do
begin
q:=a+b+c;
a:=b; b:=c; c:=q
end;
end;
writeln(q); 
end.
Это код программы, который считает количество вариантов подьема на N-ю ступеньку.
Сюда я добавил код, который вводит число сломанных ступенек и их номер:
Код:
read(k);
  for j:=1 to k do
  begin
   read (a1[j]);
  end;
Делее я считаю количество этих поломаных ступенек:
Код:
kp:=0;
  for j:=1 to k do
  begin
    kp:=kp+1;
  end;
Проверяю условие: если количество ступенек больше 2 и 3 ступеньки битые (потому как в описании сказано что заяц может ходить на следуюющую, переступать через 1 и через 2), тогда '-1'
Код:
for j:=1 to k do
  begin
    if (kp>2) and (a1[j+1]=a1[j]+1)and (a1[j+1]=a1[j+2]-1) then p:=true;
  end;
иначе вичитаю от количества ступенек битые и считаю количество вариантов
Код:
n:=n-k;
...
как-то так, но мой вариант проходит на 20%, вот и попросил помочь мне с кодом.

А как записать для моего случая (моего кода программы)
Код:
<i-я ступенька битая>
Не могу разобраться.
Очень всем благодарен.
kim-im вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск