Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Задача о кузнечике бога
СообщениеДобавлено: 15 янв 2023, 13:40 
Не в сети
Начинающий
Зарегистрирован:
15 янв 2023, 13:24
Сообщений: 1
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Условие: кузнечик стоит на точке (1, 0), он может совершать прыжки на произвольное положительное целочисленное расстояние (прыгать назад он не умеет) вдоль оси X. Необходимо найти формулу для подсчета количества траекторий, которыми кузнечик может добраться до точки (x, 0).

Зачем это всё нужно: задача представляет собой модификацию задачи о кузнечике, которая решается методом динамического программирования. Но, чтобы решить её программой, нужно вручную инициализировать начало массива, то есть ввести количество возможных траекторий для позиций i [math]\leqslant[/math] n, где i - позиция, n - максимальная длина прыжка кузнечика. К сожалению, моих познаний в комбинаторике недостаточно чтобы вывести формулу самостоятельно


Последний раз редактировалось dmitry_orlov 15 янв 2023, 14:10, всего редактировалось 2 раз(а).
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о кузнечике бога
СообщениеДобавлено: 15 янв 2023, 13:55 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
09 янв 2023, 19:09
Сообщений: 111
Откуда: село Балыко-Щучинка
Cпасибо сказано: 6
Спасибо получено:
18 раз в 17 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
dmitry_orlov
Ну навскидку вот так наверное
[math]2 + C_{x-2}^1 + C_{x-2}^2 + C_{x-2}^3 + ... + C_{x-2}^{x-3}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о кузнечике бога
СообщениеДобавлено: 15 янв 2023, 14:08 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
Что-то типа 2^(x-2)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю MihailM "Спасибо" сказали:
dmitry_orlov
 Заголовок сообщения: Re: Задача о кузнечике бога
СообщениеДобавлено: 15 янв 2023, 14:13 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Это так называемая композиция числа (см. вики).
У вас ошибка, f(5)=8 (1111, 112, 121, 211, 22, 31, 13, 4)
И, соответственно, [math]f(n)=2^{n-2}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Booker48 "Спасибо" сказали:
dmitry_orlov
 Заголовок сообщения: Re: Задача о кузнечике бога
СообщениеДобавлено: 15 янв 2023, 14:24 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
09 янв 2023, 19:09
Сообщений: 111
Откуда: село Балыко-Щучинка
Cпасибо сказано: 6
Спасибо получено:
18 раз в 17 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Ну можно и так, [math]1 + C_{x-2}^1 + C_{x-2}^2 + C_{x-2}^3 + ... + C_{x-2}^{x-3} + 1 = 2 ^ {x-2}[/math], это вроде так и доказывается через сумму биномиальных коэффициентов

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о кузнечике бога
СообщениеДобавлено: 15 янв 2023, 18:57 
Не в сети
Начинающий
Зарегистрирован:
11 ноя 2022, 10:44
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
dmitry_orlov писал(а):
Условие: кузнечик стоит на точке (1, 0), он может совершать прыжки на произвольное положительное целочисленное расстояние (прыгать назад он не умеет) вдоль оси X. Необходимо найти формулу для подсчета количества траекторий, которыми кузнечик может добраться до точки (x, 0).

Повторю то что уже сказали, но немного другими словами для наглядности.
Рассмотрим горизонтальный вектор длины [math]x-2[/math] из нулей и единиц.
Единицы соответствуют промежуточным приземлениям кузнечика.
Количество разных векторов, т.е. количество разных траекторий кузнечика, равно [math]2^{x-2}[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 6 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Цветок Бога Иисуса Христа

в форуме Палата №6

ammo77

58

1154

14 июн 2020, 02:27

Теория вероятности: задача про шары и задача про точку

в форуме Теория вероятностей

AdmiralAnanas

6

484

02 окт 2021, 01:43

Задача на построение. Корректна ли задача?

в форуме Геометрия

Student Studentovich

9

663

19 июл 2020, 19:17

Задача

в форуме Теория вероятностей

andre12344333

1

397

13 янв 2017, 16:48

Задача

в форуме Дискретная математика, Теория множеств и Логика

Sweet_blood

1

327

21 ноя 2014, 23:27

Задача ТВР

в форуме Комбинаторика и Теория вероятностей

rangersdark

5

795

25 янв 2017, 05:18

Задача №11

в форуме Интересные задачи участников форума MHP

andrei

14

984

26 янв 2017, 14:00

Задача

в форуме Теория вероятностей

Sea canary

1

189

05 сен 2020, 18:16

Задача №24

в форуме Интересные задачи участников форума MHP

andrei

1

432

24 авг 2017, 14:41

Задача

в форуме Комбинаторика и Теория вероятностей

DmitriyONE

3

476

17 авг 2017, 20:45


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved