Игры. Домино. Задано число n, 1<=n<=4. Подсчитать количество различных последовательностей ("рыба"), которые возможны в домино с очками от 0 до n.

  • ID: 46521 
  • 20 страниц

Содержание:


1. Условие задачи

Игры. Домино.

Задано число n, 1<=n<=4. Подсчитать количество различных последовательностей ("рыба"), которые возможны в домино с очками от 0 до n. 2. Анализ задачи

n – максимальное число, указанное на кости домино. n, n<=4.

b – набор домино, где - кость домино. Максимальное число костей для n=4 составляет 16 штук.

count - количество комбинаций для заданного n. res, – один из вариантов набора домино.

3. Структуры данных, используемые для представления исходных данных и результатов задачи.

Внешнее представление:

<Максимальное число на кости домино> :: = натуральное число от 1 до 4.

<Очко> :: = натуральное число 0..4.

Внешнее представление:

<Количество комбинаций> ::= натуральное число.

<Комбинация домино> :: = {<кость домино>}.

4. Укрупненный алгоритм решения задачи.

Алгоритм рекурсивный реализован в виде функции .

j – номер текущей добавляемой кости домино

k – номер позиции, куда добавляем кость (оно же является количеством костей +1 в комбинации домино).

count_k – общее количество костей в наборе.

5. Структура программы.

Пограмма разбита на подпрограммы. Реализована в одном файле domino.cpp.

Главная функция main:

– назначение:

определение входных и выходных данных задачи, ввод входных данных, просмотр набора домино и подсчет количества комбинаций, вывод результатов на экран и файл.

– прототип функции: void main ( )

6. Текст программы на языке Си.

#include <stdio.h>

#include <conio.h>

... 7. Набор тестов (в форме, соответствующей предметной области задачи)

Тест 1

Назначение: проверка допустимости n.

8. Результаты работы программы.

Тест 1

Тест 2

Содержимое domino.txt

9. Литература.

Андерсон Дж. Дискретная математика и комбинаторика. – М.; СПб.; Киев: Вильямс, 2004.

Дискретная математика: алгоритмы. http://rain.ifmo.ru/cat/view.php/theory/graph-circuits-cuts/hamiltonian-2005

Нахождение Эйлерова пути за O (M) http://e-maxx.ru/algo/euler_path

Дискретная математика. Алгоритмы: Перебор перестановок. http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000

3. Хиценко В.П., Шапошникова Т.А. Практикум на ЭВМ. Алгоритмы: учеб. пособие. – Новосибирск: НГТУ, 2004.