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

Олимпиадная задача - движение фишки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 02:17     Олимпиадная задача - движение фишки #1
Есть вот такая задача:
Код
/*Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.

Пример. N=3, K=2

Возможные пути:

1,1,1

1,2

2,1

Ответ: 3.*/
Я решил её своим способом.
А вот решение которое даётся:
Код
/*Обозначим через S(i) количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим теперь, что для любого j от 1 до i известны значения величин S(j). Задача состоит в определении правила вычисления значения S(i+1), используя значения известных величин. Легко заметить, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. Следовательно,

S(i+1)=S(i)+S(i-1)+...+S(i-k).

Таким образом, вычисляя последовательно значения величин S(1), S(2),..., S(N) по описанному выше правилу, получаем значение S(N), которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.*/
Соответственно я данное решение записываю так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void run {
n=readInt();
k=readInt();
println(S(n,k));
}
int Sum(int n, int k){
        n--;
        int sum=0;
        if(n==1) return 1;
        if(n<=0) return 0;
        for(int i=0; i<=k; i++){
        sum+=Sum(n-i,k);
        }
        return sum;
}
И в результате оно работает не правильно, я мучаюсь уже два часа!!! Пожалуйста помогите, плюсы кидаю всем, если хоть кого-то это мотивирует(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2012, 02:17     Олимпиадная задача - движение фишки
Посмотрите здесь:

C++ Олимпиадная задача на числа
Олимпиадная задача C++
C++ Олимпиадная задача
Олимпиадная задача по программированию C++
Олимпиадная задача C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 03:17     Олимпиадная задача - движение фишки #2
Цитата Сообщение от kebal Посмотреть сообщение
if(n==1) return 1;
таким образом вы задали S(1). А кто задаст S(2)?
Да и код читается ужасно. Чем проще пишите, тем больше программистов, которые увидят ваш код, скажут спасибо. Рекурсия достаточно тяжелая операция. Ее использование оправдано в очень малом числе случаев. Я бы ее здесь вообще не использовал.

Пы/Сы: последовательность Фибоначчи знаете?
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 03:46  [ТС]     Олимпиадная задача - движение фишки #3
А вы подставьте n=2, тогда увидите, что Sum(2) появится рекурсивно и его не нужно задавать, ведь в этом и есть суть.
А вообще ошибка была в моем коде. Код, который постом выше правилен.
Я как раз попытался сделать без рекурсии и вот тогда-то не получается!
Да, последовательность Фибоначчи знаю.
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 03:52     Олимпиадная задача - движение фишки #4
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
int Sum(int n, int k){
        int sum=0;
        if(n==2) return 2;
        if(n==1) return 1;
        if(n<=0) return 0;
        for(int i=1; i<=k; i++){
        sum+=Sum(n-i,k);
        }
        return sum;
}

Не уверен, что на других тестах не упадет.
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 04:06  [ТС]     Олимпиадная задача - движение фишки #5
У вас не работает для n=2; k=1;
У вас ошибка в том, что как раз присваиваиваете S(2)=2;
А вот так уже всё будет работать:
C++
1
2
3
4
5
6
7
8
9
10
int Sum(int n, int k){
        n--;
        int sum=0;
        if(n==1) return 1;
        if(n<=0) return 0;
        for(int i=0; i<=k; i++){
        sum+=Sum(n-i,k);
        }
        return sum;
}
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 04:14     Олимпиадная задача - движение фишки #6
kebal, а что будет, если n=k=3? (используя ваш код)
Дело в том, что вы не можете задать рекурсивно первые к эл-тов. Вспомните фибонначи.
Однако, первые к эл-тов это степени 2ки, начиная с 0-ой, ИМХО.
Пы/Сы: давно не спал, так что проверяйте, что я пишу)
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 04:25  [ТС]     Олимпиадная задача - движение фишки #7
Упс, извиняюсь, я всё продолжаю копировать неправильный код, путаюсь.
Вот правильный:
C++
1
2
3
4
5
6
7
8
9
10
int Sum(int n, int k){
        int sum=0;
        if(n==1) return 1;
        if(n==0) return 1;
        if(n<0) return 0;
        for(int i=0; i<k; i++){
        sum+=Sum(n-1-i,k);
        }
        return sum;
    }
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 04:27     Олимпиадная задача - движение фишки #8
такой контр-пример: n=0, k=100500

upd: а, может быть, и верно.
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 04:32  [ТС]     Олимпиадная задача - движение фишки #9
Фишка идёт по полю. Значит поле существует. Также фишка не может пройти больше, чем само поле. Она ведь улетит неизвестно куда. Поэтому k<=n;
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 05:14     Олимпиадная задача - движение фишки #10
Ну вообще к может быть больше n, т.к. это не противоречит условию задачи. Просто не используйте шаги больше длины поля и все. А про 0 верно. Только вот до сих пор не могу доказать корректность решения. Пора спать, видно.

Добавлено через 20 минут
C
1
2
3
4
5
6
7
8
9
10
int *S;
S = (int *) malloc (n * syzeof(int));
int i;
for (i = 1; i <= k; ++i) 
  S[i] = pow (2, i - 1);
for (; i <= n; ++i) {
  S[i] = 0;
  for (int j = 1; j <= k; ++j)
    if ((i - j) > 0) S[i] += S[i - j];
}
Я бы так писал. Не люблю рекурсию.
Вот вся программа:
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <math.h>
 
int main () {
int n = 5;
int k = 3;
 
int S[100];
 
int i;
for (i = 1; i <= k; ++i) 
  S[i] = pow (2.0, i - 1);
for (; i <= n; ++i) {
  S[i] = 0;
  for (int j = 1; j <= k; ++j)
    if ((i - j) > 0) S[i] += S[i - j];
}
printf ("%d\n", S[n]);
}
n, k было лень с клавиатуры считывать
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 13:58  [ТС]     Олимпиадная задача - движение фишки #11
А разве твоя программа работает? Она выдаёт совершенно другие результаты.
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 14:33     Олимпиадная задача - движение фишки #12
На каком тесте валится?
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 14:57  [ТС]     Олимпиадная задача - движение фишки #13
На любом абсолютно. 3.2; 3.3; 3.1; 4.2;
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 15:07     Олимпиадная задача - движение фишки #14
Кликните здесь для просмотра всего текста
Олимпиадная задача - движение фишкиОлимпиадная задача - движение фишкиОлимпиадная задача - движение фишки

Я просто скопировал и запустил.
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 18:44  [ТС]     Олимпиадная задача - движение фишки #15
Конечно работает, ты добавил scanf(i), а до этого не было, спасибо
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 19:18     Олимпиадная задача - движение фишки #16
kebal, дык если бы я писал в unix - системе, scanf был бы не нужен. Там консоль не смеет игнорировать пользователя. А в windows приходится просить её остаться)
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 19:24  [ТС]     Олимпиадная задача - движение фишки #17
Упс, это моя ошибка. Проверю ещё. Если scanf нужен ток чтобы остаться в системе, то дело тогда не в этом, ведь я тоже полностью скопировал код, а результаты даёт другие)
Нашёл ошибку,всё работает
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 19:27     Олимпиадная задача - движение фишки #18
Я сейчас не понял, чей вариант-то правильный? На каком тесте результаты расходятся?

Добавлено через 53 секунды
Мне уже стыдно становится, что так долго над простенькой программкой бьюсь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2012, 19:36     Олимпиадная задача - движение фишки
Еще ссылки по теме:

Задача на дп (олимпиадная) C++
C++ Олимпиадная задача
C++ C++. Олимпиадная задача

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

Или воспользуйтесь поиском по форуму:
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 19:36  [ТС]     Олимпиадная задача - движение фишки #19
всё работает
Yandex
Объявления
15.11.2012, 19:36     Олимпиадная задача - движение фишки
Ответ Создать тему
Опции темы

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