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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
#1

Заяц на ступеньках(Задача) - C++

22.01.2013, 22:52. Просмотров 1787. Ответов 9
Метки нет (Все метки)

Не могу решить задачу:
Вверху на лестнице, которая имеет N ступенек, стоит заяц, который начинает прыгать сверху вниз по ступенькам. Заяц может прыгнуть на следующую ступеньку через одну и через две.Просчитать количество всех возможных маршрутов зайца с вершины до земли.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2013, 22:52     Заяц на ступеньках(Задача)
Посмотрите здесь:

"Красный Тигр" vs. "Желтый Заяц". А каким будет 3005 год? C++
Волк заяц и коза C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1887 / 1742 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
22.01.2013, 23:06     Заяц на ступеньках(Задача) #2
число фибонначи=количество путей.
а... хотя нет. через одну это же значит с первой на третью? Тогда нет.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <math.h>
int main(){
    const int N=10;
    int ladder[N];
    ladder[0]=1;
    ladder[1]=0;
    ladder[2]=1;
    for (int i=3; i<N; i++)
        ladder[i]=ladder[i-2]+ladder[i-3];
    printf("result is %d", ladder[N-1]);
return 0;
}
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:08  [ТС]     Заяц на ступеньках(Задача) #3
А поподробнее можно?
Kuzia domovenok
1887 / 1742 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
22.01.2013, 23:13     Заяц на ступеньках(Задача) #4
массив "лестница" содержит числа
значение элемента массива равно количеству способов запрыгнуть на ступеньку с этим номером.
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:23  [ТС]     Заяц на ступеньках(Задача) #5
Допустим, но как рассчитать значения каждого массива?

Добавлено через 5 минут
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ladder[0]=1;
* * ladder[1]=0;
* * ladder[2]=1;
Что это значит?
На сколько я понимаю 0елемент(1ступенька)-1путь
1елемент(2ступеньки)-2пути
2елемент(3ступеньки)-4пути
а что значит то, что Вы написали?

Добавлено через 49 секунд
Он же прыгает на одну через одну и через две.
Kuzia domovenok
1887 / 1742 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
22.01.2013, 23:27     Заяц на ступеньках(Задача) #6
сколько же способов есть, чтоб запрыгнуть на i-ступеньку?
по большому счёту 2
1) запрыгнуть на i-2 ю ступеньку и сделать прыжок длиной "через ступеньку"
2) запрыгнуть на i-3 ю ступеньку и сделать прыжок длиной "через две ступеньки"

то есть чтобы испробовать ВСЕ ВОЗМОЖНЫЕ способы дойти до i-й ступеньки надо
1) пройти A штук всевозможных путей до i-2 й ступеньки, завершив их прыжком длины "через ступеньку"
2) пройти В штук всевозможных путей до i-3 й ступеньки, завершив их прыжком длины "через 2 ступеньки"
Получаем всего А+В способов дойти до i-й ступеньки

ты не говорил, что можно на одну прыгать
если на одну можно, то тогда так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <math.h>
int main(){
    const int N=10;
    int ladder[N];
    ladder[0]=1;
    ladder[1]=1;
    ladder[2]=2;
    for (int i=3; i<N; i++)
        ladder[i]=ladder[i-1]+ladder[i-2]+ladder[i-3];
    printf("result is %d ", ladder[N-1]);
return 0;
}
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:34  [ТС]     Заяц на ступеньках(Задача) #7
В условии можно соскочить на 1 ступеньку то есть i-1. Не так ли?
Kuzia domovenok
1887 / 1742 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
22.01.2013, 23:37     Заяц на ступеньках(Задача) #8
ну да, я исправил, но смысл аналогичен.

сколько же способов есть, чтоб запрыгнуть на i-ступеньку?
по большому счёту 3 типа
1) запрыгнуть на i-1 ю ступеньку и сделать прыжок длиной "на след. ступеньку"
2) запрыгнуть на i-2 ю ступеньку и сделать прыжок длиной "через ступеньку"
3) запрыгнуть на i-3 ю ступеньку и сделать прыжок длиной "через две ступеньки"

то есть чтобы испробовать ВСЕ ВОЗМОЖНЫЕ способы дойти до i-й ступеньки надо
1) пройти A=ladder[i-1] штук всевозможных путей до i-2 й ступеньки, завершив их прыжком длины "на след. ступеньку"
1) пройти В=ladder[i-2] штук всевозможных путей до i-2 й ступеньки, завершив их прыжком длины "через ступеньку"
2) пройти С=ladder[i-3] штук всевозможных путей до i-3 й ступеньки, завершив их прыжком длины "через 2 ступеньки"
Получаем всего А+В+С способов дойти до i-й ступеньки
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:52  [ТС]     Заяц на ступеньках(Задача) #9
А 0,1 и 2 элементы массива-это же количество допустимых вариантов пути?

Добавлено через 11 минут
Я стараюсь понять, спасибо большое!
Kuzia domovenok
1887 / 1742 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
23.01.2013, 00:01     Заяц на ступеньках(Задача) #10
ну да, их мы заполняем вручную, т.к. выражение
ladder[i]=ladder[i-1]+ladder[i-2]+ladder[i-3];
для них выйдет за границы массива.
Впрочем это можно автоматизировать

Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <math.h>
int main(){
    const int N=10;
    int ladder[N];
    ladder[0]=1;
    for (int i=1; i<N; i++){
        ladder[i]=0;
        for (int j=(i>3)?i-3:0; j<i; j++)
             ladder[i]+=ladder[j];
    }
    printf("result is %d ", ladder[N-1]);
return 0;
}
Yandex
Объявления
23.01.2013, 00:01     Заяц на ступеньках(Задача)
Ответ Создать тему
Опции темы

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