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

Сколькими способами человек может попасть в магазин - C++

Восстановить пароль Регистрация
 
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
07.09.2014, 00:35     Сколькими способами человек может попасть в магазин #1
МАГАЗИН

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

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

Входные данные

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

Выходные данные

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

Примеры
INPUT.TXT OUTPUT.TXT
2 4 ________________ 2
5 5 ________________ 1

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Привет, ребята.
У меня вот такой вопрос.
Есть у меня такая функция.
Нужно, чтобы f увеличивалась при попадании в максимальный уровень рекурсии (когда i=0)
Пробовал и глобально и через указатели - ничего.
C++
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
26
27
28
29
30
31
void recur(int i,int t,int a[37][50]) {
    int p=f;
    if (i==0) {
        if (t==k) {
            f+=1;
            exit;
        }
    }
    if (t+i<=k) {
        if (a[i-1][t+1]==0) {
        recur(i-1,t+1,a);
        }
    }
        else if (a[i-1][t+1]>0) {
            f+=a[i-1][t+1];
        }
     if (t+i<=k) {
       if (a[i+1][t+1]==0) {
        recur(i+1,t+1,a);
       }
     }
       else if (a[i+1][t+1]>0) {
           f+=a[i+1][t+1];
       }
       if (p!=f) {
           a[i][t]=f-p;
       }
       else {
           a[i][t]=-1;
       }
     }
Как бы я не делал, что бы я не объявлял - переменная f все равно не увеличивается. Либо увеличивается, но только на один. (Пробовал писать и f++ и f+=1)
Вот полный код
Кликните здесь для просмотра всего текста

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <iostream>
using namespace std;
int n,k;
int f=0;
void recur(int i,int t,int a[37][50]) {
    int p=f;
    if (i==0) {
        if (t==k) {
            f+=1;
            exit;
        }
    }
    if (t+i<=k) {
        if (a[i-1][t+1]==0) {
        recur(i-1,t+1,a);
        }
    }
        else if (a[i-1][t+1]>0) {
            f+=a[i-1][t+1];
        }
     if (t+i<=k) {
       if (a[i+1][t+1]==0) {
        recur(i+1,t+1,a);
       }
     }
       else if (a[i+1][t+1]>0) {
           f+=a[i+1][t+1];
       }
       if (p!=f) {
           a[i][t]=f-p;
       }
       else {
           a[i][t]=-1;
       }
     }
 
int main() {
 int a[37][50]={0};
 cin >> n >> k;
 recur(n,0,a); 
 cout << f;
 return 0;
}


Добавлено через 1 минуту
Пробовал тестить так.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
void f(int i,int *ptr) {
    if (i==0) return;
    else {
        cout << "Работает" << endl;
        cout << *ptr << endl;
        f(i-1,ptr);
    }
}
int main() {
 
int *ptr = new int;
*ptr = 3;
f(6,ptr);
cout << *ptr;
delete(ptr);
}
Получается, а когда делал с указателями в той программе - больше 1 не повышалось, хотя последние уровни рекурсии достигались (проверял с помощью cout).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2014, 00:35     Сколькими способами человек может попасть в магазин
Посмотрите здесь:

C++ Сколькими способами можно отобрать команду в составе 5 человек из 8 кандидатов;из 10 кандидатов; из 11 кандидатов? Подсчет количества способов отбора
C++ Требуется вычислить сколькими способами можно получить строку В из строки А
Вложенные циклы: Сколькими способами гирями данного набора можно составить вес в v грамм C++
C++ Задача на динамическое программирование(скорее всего) (сколькими способами в сумме получить N, без подряд идущих одинаковых чисел)
Самолет может поднять 750 кг, если средний вес человека 70кг. Посчитать сколько человек может поднять самолет? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rikimaru2013
C++ Game Dev
 Аватар для rikimaru2013
2133 / 966 / 222
Регистрация: 30.11.2013
Сообщений: 3,223
07.09.2014, 00:45     Сколькими способами человек может попасть в магазин #2
CrazzyBeer, и что делает ваша зверь программа?
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
07.09.2014, 01:24  [ТС]     Сколькими способами человек может попасть в магазин #3
Решает задачу "Магазин". Номер 169 на a c m p.
Правда она пока ничего не решает. Я переписывал с Pascal и встретился с объявленной проблемой. Помучился чуток и решил спросить у вас.
Мне бы узнать, почему переменная не увеличивается...
rikimaru2013
C++ Game Dev
 Аватар для rikimaru2013
2133 / 966 / 222
Регистрация: 30.11.2013
Сообщений: 3,223
07.09.2014, 01:26     Сколькими способами человек может попасть в магазин #4
CrazzyBeer, опишите задачу. Тоже хочу решить её. Врядли решение задачи такое глупое как у вас.
К примеру: из-за 9 строки в 17-ую не зайдёт никогда. 2 глобальных переменные зачем-то
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
07.09.2014, 01:30  [ТС]     Сколькими способами человек может попасть в магазин #5
Дело в том, что я уже её сдал и я не думал, что вы тут в "С++ для начинающих" называете коды глупыми.
Я просто неверно переписал.
Сейчас попробую поставить вместо exit - return.

Добавлено через 1 минуту
На счет задачи. Зайдите, да и прочитайте.
Решение сводится до поиска в глубину с ленивой динамикой.
rikimaru2013
C++ Game Dev
 Аватар для rikimaru2013
2133 / 966 / 222
Регистрация: 30.11.2013
Сообщений: 3,223
07.09.2014, 01:36     Сколькими способами человек может попасть в магазин #6
Да, именно глупыми! Если "передрать" с интернета и не понимать, что буквы 'Z' и 'z' не выведутся никогда. Это глупо!
C++
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
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
void Foo(int x)
{
   if(x == 0)
      return;
   if(x < 5)
   {
      cout << "Q";
      return Foo(x-1);
   }
   else
   {
      cout << "q";
      return Foo(x-1);
   }
   if(x < 5)
   {
      cout << "Z";
      return Foo(x-1);
   }
   else
   {
      cout << "z";
      return Foo(x-1);
   }
}
 
int main()
{
     Foo(10);
     return 0;
}
И опишите задачку про "магазин" - мне ж интересно.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.09.2014, 09:59     Сколькими способами человек может попасть в магазин #7
как-то у вас все запутано. можно, например, так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
i64 get(int x, int kk) {
    if(dp[x][kk] == -1) {
        dp[x][kk] = 0;
        if(kk > 0 && kk <= k) {
            if(x >= 2)
                dp[x][kk] += get(x-1, kk-1);
            dp[x][kk] += get(x+1, kk-1);
        }
    }
    return dp[x][kk];
}
 
int main() {
...
    cout << get(0, k) << endl;
...
}
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
07.09.2014, 13:36  [ТС]     Сколькими способами человек может попасть в магазин #8
Извините, если кто-то меня не понял. Сейчас все уточню.
1. Я создал тему в разделе "С++ для начинающих", соответственно, я начинающий, который просидел часа два над кодом и ничего не смог сделать.
2. Мне не нужно само решение задачи, мне нужно было просто понять, почему значение переменной не менялось.
3. Запутанно потому, что обычным поиском в глубину не обойтись, вот и использовал ленивую динамику. Согласен, программу можно сделать лучше, не смею с этим спорить. Но проблема то не в этом.
Может я как-то неправильно выхожу из подпрограммы, когда достигаю магазина?

Добавлено через 3 минуты
Я просто привык в Pascal выходить из подпрограммы с помощью "Exit", а тут может существуют какие-то другие возможности.

Добавлено через 24 минуты
А она точно работает?
Вы не задали условие, когда какой-то ячейке массива увеличиваться. Получается, что там всегда +0 будет, я прав?

Добавлено через 1 минуту
rikimaru2013, извиняюсь, но я ничего не передрал, все вышеописанные коды - мои, я сам их писал и ничьими идеями я не пользовался.
А вы можете наконец объяснить, почему эти буквы выводится не будут?!

Добавлено через 24 минуты
Вот.
C++
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
#include <stdio.h>
#include <iostream>
using namespace std;
 int a[37][50]={0};
 int n,k;
long rec(int i, int t) {
    if (i==0) {
        if (t==k) return 1;
        else return 0;
    }
    if  (t+i<=k) {
        if (a[i][t]==0) {
            a[i][t]+=rec(i-1,t+1);
            a[i][t]+=rec(i+1,t+1);
        }
    }
        return a[i][t];
    }
int main() {
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
 cin >> n >> k;
 cout << rec(n,0);
 return 0;
}
Решение прошло все тесты. Спасибо огромное salam. Хотелось бы еще узнать, как избавиться от глобальных переменных? Объявить их в декларативной части функции?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.09.2014, 14:53     Сколькими способами человек может попасть в магазин #9
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
Хотелось бы еще узнать, как избавиться от глобальных переменных?
видимо их стоит объявлять в main() и передавать при необходимости как параметр. в данном случае, вызывая rec(), передавать не только i и t, но еще и n, и k.
ну и пара замечаний общих.
1.если бы состояний динамики было больше, то массив а[] нужно было бы объявить статическим (если бы он объявлялся в функции main())
C++
1
static int a[40][50];
почитайте про static в книгах. вообще полезно понимать, где программа выделяет вам память.
2. вы сделали распространенную ошибку: объявили массив а[] как int, а из функции rec() возвращаете long. очевидно, нужно возвращать тот тип, которого у вас массив.
2.1. не всегда int и long - разные по объему типы. надо обращать внимание на это, когда пишешь задачу.
3. не очень понятно, почему ваше решение не упало. вроде как вы можете прошагать k шагов сразу из n-ой клетки. тогда ваших a[][50] может не хватить. вообще не экономьте память, когда пишете олимпиадную задачу (в рамках ограничения на память). это пустая трата времени.
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
07.09.2014, 15:55  [ТС]     Сколькими способами человек может попасть в магазин #10
0. А массив можно и не передавать функции?
3. Я это учел. В ограничениях n<= k <= 37. Это значит, что N не может быть больше 37. Чтобы напрямую попасть из N в 0 - нужно 37 шагов, тобишь , если уходить от магазина, а не к магазину, то где-то на оно выйдет само, так как t+i<=k уже не будет выполняться.
Пы.Сы.
Лучше объявлять динамически?

C++
1
2
int *arr = new long[50];
delete []arr;
И потом функции передавать так?
C++
1
void func(long[50] *point)
Добавлено через 6 минут
Извините, что-то вопросы у меня слишком очевидные. Просто мне важно разобраться и потом уже пойти в среду программирования и поиграться с новыми знаниями.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.09.2014, 16:34     Сколькими способами человек может попасть в магазин #11
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
А массив можно и не передавать функции?
если он глобальный, то передавать не надо. если он описан в main(), то, конечно, его нужно передавать как параметр.
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
Я это учел. В ограничениях n<= k <= 37. Это значит, что N не может быть больше 37. Чтобы напрямую попасть из N в 0 - нужно 37 шагов, тобишь , если уходить от магазина, а не к магазину, то где-то на оно выйдет само, так как t+i<=k уже не будет выполняться.
я ничего не понял. если вы осознавали здесь возможность бага - ок. я хотел только обратить внимание.
Цитата Сообщение от CrazzyBeer Посмотреть сообщение
Лучше объявлять динамически?
если у вас предостаточно памяти, то лучше сразу выделить с запасом и забыть. динамическое выделение происходит на этапе выполнения программы. оно стоит времени, которое может быть критично в отличии от памяти. особенно, когда вы много раз выделяете понемногу.
CrazzyBeer
 Аватар для CrazzyBeer
3 / 3 / 2
Регистрация: 24.03.2014
Сообщений: 65
07.09.2014, 22:16  [ТС]     Сколькими способами человек может попасть в магазин #12
Извиняюсь, думал, что написал число, а , оказывается, не написал
Цитата Сообщение от salam Посмотреть сообщение
Сообщение от CrazzyBeer
Я это учел. В ограничениях n<= k <= 37. Это значит, что N не может быть больше 37. Чтобы напрямую попасть из N в 0 - нужно 37 шагов, тобишь , если уходить от магазина, а не к магазину, то где-то на оно выйдет само, так как t+i<=k уже не будет выполняться.
я ничего не понял. если вы осознавали здесь возможность бага - ок. я хотел только обратить внимание.
если уходить от магазина, а не к магазину, то где-то 50 на оно выйдет само
Mr.X
Эксперт С++
 Аватар для Mr.X
2796 / 1572 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
08.09.2014, 09:48     Сколькими способами человек может попасть в магазин #13
C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/////////////////////////////////////////////////////////////////////////////////////////
//МАГАЗИН
//
//На расстоянии N шагов от магазина стоит человек. Каждую минуту он выбирает, куда сделать шаг: 
//к магазину или в противоположном направлении.
//
//Требуется написать программу, которая определит, сколькими способами он может попасть в магазин, 
//пройдя ровно K шагов и оказавшись в магазине только после выполнения последнего шага.
//
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл INPUT.TXT содержит 2 числа n и k, записанные через пробел. Известно, что 1 <= N <= K <= 37.
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//Выходной файл OUTPUT.TXT должен содержать одно число – количество способов попадания в магазин.
//
//Примеры
//INPUT.TXT OUTPUT.TXT
//2 4 ________________ 2
//5 5 ________________ 1
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <map>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::pair   < int,                      int         >   T_dist_and_steps_count;
typedef long long                                               T_variants;
typedef std::map    < T_dist_and_steps_count,   T_variants  >   T_variants_for_dist_and_steps_count;
/////////////////////////////////////////////////////////////////////////////////////////
T_variants  count_variants_for_distance_and_steps_count
    (
        int                                         distance,
        int                                         steps_count,
        T_variants_for_dist_and_steps_count     &   variants_for_dist_and_steps_count
    )
{
    if  (
            ( distance + steps_count ) % 2
        )
    {
        return  0;
    }
    else
    {
        auto    dist_and_steps_count    =   std::make_pair( distance, steps_count );
 
        if  (
                    variants_for_dist_and_steps_count.find  ( dist_and_steps_count )
                ==  variants_for_dist_and_steps_count.end   ()
            )
        {
                variants_for_dist_and_steps_count[ dist_and_steps_count ]
            =   distance    ==  0
                    ?   0
                    :   distance    ==  steps_count
                            ?   1
                            :       count_variants_for_distance_and_steps_count
                                        (
                                            distance        -   1,
                                            steps_count     -   1,
                                            variants_for_dist_and_steps_count
                                        )
 
                                +   count_variants_for_distance_and_steps_count
                                        (
                                            distance        +   1,
                                            steps_count     -   1,
                                            variants_for_dist_and_steps_count
                                        );
        }//if
 
        return  variants_for_dist_and_steps_count[ dist_and_steps_count ];
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    for(;;)
    {
        T_variants_for_dist_and_steps_count     variants_for_dist_and_steps_count;
 
        std::cout   <<  "n = ";
        int     n   =   0;
        std::cin    >>  n;
 
        std::cout   <<  "k = ";
        int     k   =   0;
        std::cin    >>  k;
 
        std::cout   <<  count_variants_for_distance_and_steps_count
                            (
                                n,
                                k,
                                variants_for_dist_and_steps_count
                            )
 
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.09.2014, 16:07     Сколькими способами человек может попасть в магазин
Еще ссылки по теме:

C++ Написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов
C++ Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол
Сколькими способами можно разменять 100 000 рублей на монеты 1, 2, 5 рублей? C++

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

Или воспользуйтесь поиском по форуму:
CrazzyBeer
08.09.2014, 16:07  [ТС]     Сколькими способами человек может попасть в магазин
  #14

Не по теме:

Боженьки, что это за бандура?

Yandex
Объявления
08.09.2014, 16:07     Сколькими способами человек может попасть в магазин
Ответ Создать тему
Опции темы

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