Динамическое программирование

@Condor_Palenski · Регистрация: 10.04.2015

Студворк — интернет-сервис помощи студентам

Приветствую, форумчане. Так уж вышло, что жизнь свела меня с динамическим программированием.
Есть задача: Стрелок стреляет по мишеням. Найти вероятность поражения им 10 мишеней при наличии 13 патронов, если вероятность попадания по мишени составляет 0.5.
Необходимо реализовать алгоритм динамического программирования(на любом языке, но желательно C++, но я и от Паскаля или C# не откажусь). Я нашел решение в инете, но есть кое-какие непонятки, а именно:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "stdafx.h"
#include <iostream> 
#include <ctime> 
using namespace std;
int main()
{
    srand(time(0));
    int j, k, c, n, N;
    cout << "N="; cin >> N;
    for (k = n = 0; n < N; n++)
    {
        for (c = j = 0; j < 13; j++)
        {
            if (rand() > 6553) 
                c++;
        }
        if (c>10) k++;
    }
    cout << k / float(N) << endl;
    system("pause");
    return 0;
}

все в принципе адекватно, кроме числа 6553, откуда оно взялось, случайно или на основе каких то выводов? и если подумать, верно ли решение. Спасибо заранее))

Добавлено через 16 минут
есть намеки мол 6553 это почти как 65535, тип как очень большое число...но причем здесь оно?

@Shamil1 · 08.11.2015, 14:18

Раз уж стоит задача использовать динамическое программирование, то я бы предложил такое решение:
1. Берём матрицу 14 на 14. Строки соответствуют количеству выстрелов, а столбцы - количеству поражённых мишеней. В ячейках матрицы aa[i,j] - количество исходов, при которых после i выстрелов j поражённых мишеней.
2. aa[0,0] = 1 // после нуля выстрелов у нас всегда 0 поражённых мишеней
3. После каждого выстрела количество подбитых мишеней с равной вероятностью либо остаётся прежним, либо увеличивается на 1. То есть, на каждом шаге надо выполнить:
aa[i,j] = aa[i-1,j-1] + aa[i-1,j]
4. Ответ будет в ячейке aa[13,10]

Алгоритм готов, но можно его оптимизировать по использованию памяти. На каждом шаге нам нужна только предыдущая строка. Поэтому вместо двумерного массива можно использовать два одномерных (текущая и предыдущая строки) и после каждого шага менять их местами.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	08.11.2015, 14:18
	Сообщение было отмечено Condor_Palenski как решение Решение Раз уж стоит задача использовать динамическое программирование, то я бы предложил такое решение: 1. Берём матрицу 14 на 14. Строки соответствуют количеству выстрелов, а столбцы - количеству поражённых мишеней. В ячейках матрицы aa[i,j] - количество исходов, при которых после i выстрелов j поражённых мишеней. 2. aa[0,0] = 1 // после нуля выстрелов у нас всегда 0 поражённых мишеней 3. После каждого выстрела количество подбитых мишеней с равной вероятностью либо остаётся прежним, либо увеличивается на 1. То есть, на каждом шаге надо выполнить: aa[i,j] = aa[i-1,j-1] + aa[i-1,j] 4. Ответ будет в ячейке aa[13,10] Алгоритм готов, но можно его оптимизировать по использованию памяти. На каждом шаге нам нужна только предыдущая строка. Поэтому вместо двумерного массива можно использовать два одномерных (текущая и предыдущая строки) и после каждого шага менять их местами. 1

Динамическое программирование

Решение