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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
#1

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

15.11.2012, 02:17. Просмотров 1758. Ответов 18
Метки нет (Все метки)

Есть вот такая задача:
Код
/*Фишка может двигаться по полю длины 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;
}
И в результате оно работает не правильно, я мучаюсь уже два часа!!! Пожалуйста помогите, плюсы кидаю всем, если хоть кого-то это мотивирует(
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2012, 02:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Олимпиадная задача - движение фишки (C++):

Задача про фишки на комбинаторику - C++
У Андрея есть огромное количество фишек N цветов. Он хочет выложить некоторое количество фишек в один ряд так, чтобы для любых двух...

Задача на дп (олимпиадная) - C++
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...

Олимпиадная задача - C++
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача - C++
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...

Олимпиадная задача - C++
#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; int main() { unsigned int N; cout&lt;&lt;&quot;N=&quot;;...

Олимпиадная задача - C++
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

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

Пы/Сы: последовательность Фибоначчи знаете?
1
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 03:46  [ТС] #3
А вы подставьте n=2, тогда увидите, что Sum(2) появится рекурсивно и его не нужно задавать, ведь в этом и есть суть.
А вообще ошибка была в моем коде. Код, который постом выше правилен.
Я как раз попытался сделать без рекурсии и вот тогда-то не получается!
Да, последовательность Фибоначчи знаю.
0
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;
}

Не уверен, что на других тестах не упадет.
1
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;
}
0
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 04:14 #6
kebal, а что будет, если n=k=3? (используя ваш код)
Дело в том, что вы не можете задать рекурсивно первые к эл-тов. Вспомните фибонначи.
Однако, первые к эл-тов это степени 2ки, начиная с 0-ой, ИМХО.
Пы/Сы: давно не спал, так что проверяйте, что я пишу)
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;
    }
0
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 04:27 #8
такой контр-пример: n=0, k=100500

upd: а, может быть, и верно.
0
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 04:32  [ТС] #9
Фишка идёт по полю. Значит поле существует. Также фишка не может пройти больше, чем само поле. Она ведь улетит неизвестно куда. Поэтому k<=n;
0
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 было лень с клавиатуры считывать
0
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 13:58  [ТС] #11
А разве твоя программа работает? Она выдаёт совершенно другие результаты.
0
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 14:33 #12
На каком тесте валится?
0
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 14:57  [ТС] #13
На любом абсолютно. 3.2; 3.3; 3.1; 4.2;
0
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
15.11.2012, 15:07 #14
Кликните здесь для просмотра всего текста
Олимпиадная задача - движение фишкиОлимпиадная задача - движение фишкиОлимпиадная задача - движение фишки

Я просто скопировал и запустил.
1
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
15.11.2012, 18:44  [ТС] #15
Конечно работает, ты добавил scanf(i), а до этого не было, спасибо
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2012, 18:44
Привет! Вот еще темы с ответами:

Олимпиадная задача - C++
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна из популярных социальных сетей &quot;НаМурмаре&quot; при регистрации...

C++. Олимпиадная задача - C++
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача - C++
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо с помощью графов, но какого-то...

Сладкая олимпиадная задача - C++
Дан торт который порезан на m*n равных кусков и вы хотите иметь точно один фрукт на каждом куске. Давайте обозначим f(m,n) количество...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
15.11.2012, 18:44
Ответ Создать тему
Опции темы

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