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

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

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

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

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

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

Волк заяц и коза - C++
Классическая задача про волка заяца и козу , которых нужно перевозить на другой берег так что бы коза не съела капусту а волк не съел козу....

"Красный Тигр" vs. "Желтый Заяц". А каким будет 3005 год? - C++
помогите пожалуйста решить В некоторых странах Дальнего Востока (Китае, Японии и др.) использовался (и неофициально используется в...

Заяц - Free Pascal
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке...

Заяц и дерево - Pascal
Помогите пожалуйста решить задачу. Заранее спасибо! После строительства на выбранной поляне частокола для обороны от хищников Заяц...

Заяц и дерево - Pascal ABC
После строительства на выбранной поляне частокола для обороны от хищников Заяц обнаружил, что внутри ограды оказалось огромное засохшее...

программа заяц- волк паскаль - Pascal
программа заяц- волк. дан массив 100 x 100. вводим количество зайцев и волков с клавиатуры. в массиве они размещены случайным образом....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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;
}
1
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:08  [ТС] #3
А поподробнее можно?
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
22.01.2013, 23:13 #4
массив "лестница" содержит числа
значение элемента массива равно количеству способов запрыгнуть на ступеньку с этим номером.
1
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 секунд
Он же прыгает на одну через одну и через две.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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;
}
1
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:34  [ТС] #7
В условии можно соскочить на 1 ступеньку то есть i-1. Не так ли?
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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-й ступеньки
1
piset
3 / 3 / 0
Регистрация: 22.12.2011
Сообщений: 24
22.01.2013, 23:52  [ТС] #9
А 0,1 и 2 элементы массива-это же количество допустимых вариантов пути?

Добавлено через 11 минут
Я стараюсь понять, спасибо большое!
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2013, 00:01
Привет! Вот еще темы с ответами:

Заяц вместо логотипа PHP - PHP
Либо тут что то не так либо одно из двух. :-( Качнул дистрибутив php5 с оффициального сайта, установил его как модуль, на 2 сервера, при...

Динамическое программирование заяц прыгает по ступенькам - Turbo Pascal
Не дружу я с динамическим программированием...:( В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно,...

Графика: кошка, ежик, заяц на полянке с ёлкой - PascalABC.NET
Нарисовать кошку,ежика,зайца на полянке с ёлкой.

Докажите, что рано или поздно заяц наступит лапой в ручей - Математический анализ
Заяц прыгает по окружности против часовой стрелки прыжками одинаковой длины, прич никогда не попадает в свой след. Окружность пересекает...


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

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

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