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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Erden
0 / 0 / 0
Регистрация: 06.11.2013
Сообщений: 3
#1

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

10.12.2013, 12:04. Просмотров 1061. Ответов 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

как решать эту задачу
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2013, 12:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов (C++):

Сколькими способами человек может попасть в магазин - C++
МАГАЗИН На расстоянии N шагов от магазина стоит человек. Каждую минуту он выбирает, куда сделать шаг: к магазину или в противоположном...

Написать программу, которая может угадывать числа от 0 до 100 - C++
Надо написать программу которая может угадывать числа от 0 до 100

Нужно написать рекурсивную функцию, которая определит - является ли симметричной часть строки от n, до z - C++
Нужно написать рекурсивную функцию, которая определит - является ли симметричной часть строки от n, до z. Выдает ошибку: #include...

Рекурсия. Составьте программу, которая для заданных значений n и m, определит номер оставшегося в кругу человека - C++
Пусть n человек встали в круг и получили номера от 1 до n по часовой стрелке. Затем, начиная с первого, по часовой стрелке отсчитывается m...

Напишите программу, которая определит, могут ли эти числа быть длинами сторон равнобедренного треугольника - C++
Дорогие мои, пожалуйста помогите, у меня не получается задача(( &quot;На входе три числа. Напишите программу, которая определит, могут ли эти...

Написать программу, которая определит общую сумму денежных средств - Delphi
Вот задача. &quot;Дети нашли несколько текстов, содержащих данные о величине доходов в различных денежных единицах. В каждом тексте...

1
CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
29.08.2014, 14:45 #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 с данным количеством шагов
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.08.2014, 14:45
Привет! Вот еще темы с ответами:

Надо написать программу, которая определит, принадлежит ли точка М области - Basic
Как решить 2 задачу ? надо написать программу которая определит принадлежит ли точка М области ?

Написать программу, которая по введенной дате рождения человека определит кто он по знаку зодиака - Turbo Pascal
Известно, что астрологи делят год на 12 периодов и каждому из них ставят в соответствие один из знаков Зодиака: Период Знак...

Написать программу, которая определит наличие в матрице (из нулей и единиц) одной из трёх фигур - Delphi
Двумерный массив заполнен нулями и единицами. Написать программу, которая определит наличие в массиве одной из трёх фигур: 1....

Написать программу, которая определит, за какой срок выплаченных арендатору денег составит заданную величину - Visual Basic
Помогите пожалуйста, вот условия задачи: Клиент выплачивает арендную плату в размере S руб. в месяц. За пол года арендатор увеличивает...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru