Форум программистов, компьютерный форум CyberForum.ru

Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов - C++

Восстановить пароль Регистрация
 
Erden
0 / 0 / 0
Регистрация: 06.11.2013
Сообщений: 3
10.12.2013, 12:04     Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов #1
Магазин
(Время: 1 сек. Память: 16 Мб Сложность: 34%)

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

Требуется написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов и оказавшись в магазине только после выполнения последнего шага.
Входные данные

Входной файл INPUT.TXT содержит 2 числа n и k, записанные через пробел. Известно, что 1 <= N <= K <= 37.
Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно число – количество способов попадания в магазин.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 2 4 2
2 5 5 1

как решать эту задачу
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2013, 12:04     Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов
Посмотрите здесь:

C++ Нужно написать программу которая будет вычислять факториал. В нете много подобного, но хорошего не увидел. Может у кого код завалялся.
C++ Требуется вычислить сколькими способами можно получить строку В из строки А
C++ Напишите программу, которая определит, могут ли эти числа быть длинами сторон равнобедренного треугольника
C++ Рекурсия. Составьте программу, которая для заданных значений n и m, определит номер оставшегося в кругу человека
C++ Нужно написать рекурсивную функцию, которая определит - является ли симметричной часть строки от n, до z
C++ Сколькими способами человек может попасть в магазин
C++ Составить алгоритм и программу, которая определит сколько досок надо купить, чтобы поставить сплошной забор
Составить алгоритм и программу, которая определит стоимость обоев для всей стены, если цена одного рулона X C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
29.08.2014, 14:45     Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов #2
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var n,k,f:int64;
procedure c(i,t:int64);
 begin
  if (i=0)  then begin if t=k then inc(f); exit; end;
  if t+i<=k then c(i+1,t+1) else exit;
  if t<k then c(i-1,t+1) else exit;
 end;
begin
assign(input, 'input.txt'); reset(input); 
assign(output, 'output.txt'); rewrite(output);
read(n,k);
c(n,0);
write(f);
end.
Вот попытка решения, но она проваливается по времени. Тоже интересен метод решения (чтобы работал быстро с большими ограничениями)

Добавлено через 1 час 35 минут
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var n,k,f:int64;
    a:array[0..37,0..50] of integer;
procedure c(i,t,p:int64);
 begin
  p:=f;
  if (i=0)  then begin if t=k then inc(f); exit; end;
  if t+i<=k then
    begin
     if a[i-1,t+1]=0 then c(i-1,t+1,p) 
       else if a[i-1,t+1]>0 then inc(f,a[i-1,t+1]) 
    end;
  if t+i<=k then
    begin
     if a[i+1,t+1]=0 then c(i+1,t+1,p) 
       else if a[i+1,t+1]>0 then inc(f,a[i+1,t+1]) 
    end;
  if p<>f then a[i,t]:=f-p else a[i,t]:=-1;
 end;
begin
assign(input, 'input.txt'); reset(input); 
assign(output, 'output.txt'); rewrite(output);
read(n,k);
c(n,0,0);
write(f);
end.
Пожалуйста. Решение прошло все тесты.
Используется метод ленивой динамики. Для каждой вершины запоминается, сколько раз можно из неё попасть в вершину 0 с данным количеством шагов
Yandex
Объявления
29.08.2014, 14:45     Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов
Ответ Создать тему
Опции темы

Текущее время: 23:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru