Решение задачи о циферблате (о клавиатуре) телефона. Программа на С++ (Builder 6)
Похожие задачи можно найти на авторитетном сайте «olympiads.ru» …
Скачать проект (исходный код)
в виде зашифрованного архива. Пароль в рассылке.
Все помнят, как выглядит клавиатура мобильного телефона…?
По условию задачи, телефонный номер может набираться только «ходом конем» (или буквой Г).
Вопрос1: Сколько вариантов номеров можно набрать таким способом при заданной длине номера (количестве цифр в телефонном номере) n ?
Или упрощенная…
Вопрос2: Сколько вариантов номеров можно набрать таким способом при заданной длине номера (количестве цифр в телефонном номере) n , начиная с заданной цифры р ?
Решение:
Как известно, лучше всего компьютер умеет считать варианты. Складывая единичку к единичке, в отличие от человека, он практически не ошибается…
Вот и надо его этим озадачить…
Понятно, что с определенной кнопки за один шаг можно выполнить переход только на некоторые другие кнопки. Так с кнопки 1, таких переходов может быть только два (на клавиши 6 и 8). С кнопки 4, возможно три перехода (3,9,0). А с кнопки 5 вариантов нет. Отсутствуют начисто. Впрочем, на нее и встать то наш конь не сможет, если началом выбрана любая другая кнопка.
Следовательно, за два шага с заданной кнопки, наш конь может проскакать различными путями … сумму вариантов (за один шаг) с тех кнопок, на которые он способен попасть с заданной…
Если создадим двумерный массив cou[i][j] , то индексом i назначим номер начальной кнопки клавиатуры (первой цифры номера), а индексом j – количество ходов (длина номера минус 1).
Так cou[1][2]= cou[6][1]+ cou[8][1], а cou[4][2]= cou[3][1]+ cou[9][1]+ cou[0][1].
Идея я думаю понятна…
Например, для трех шагов:
cou[1][3]= cou[6][2]+ cou[8][2], а cou[4][3]= cou[3][2]+ cou[9][2]+ cou[0][2].
То есть, каждый следующий шаг заполнения (уровень) массива будет требовать данные с предыдущего уровня этого же массива. Нулевой и первый уровень массива, конечно, придется заполнить нам (это как константы, которые зависят от взаимного расположения кнопок на клавиатуре)…
// нулевой уровень - если цифр в номере всего 1
for (int i=0; i<10; i++)
cou[i][0]=1;
//первый уровень - если цифр в номере всего 2
cou[0][1]=2; cou[1][1]=2; cou[2][1]=2; cou[3][1]=2; cou[4][1]=3;
cou[5][1]=0; cou[6][1]=3; cou[7][1]=2; cou[8][1]=2; cou[9][1]=2;
Все! Можно поручать компьютеру, в цикле рассчитать массив.
Здесь j - количество ходов конем, а n - количество цифр в номере (задано).
for (unsigned int j=2; j<n; j++) //более высокие уровни
{
cou[0][j] = cou[4][j-1]+cou[6][j-1];
cou[1][j] = cou[6][j-1]+cou[8][j-1];
cou[2][j] = cou[7][j-1]+cou[9][j-1];
cou[3][j] = cou[4][j-1]+cou[8][j-1];
cou[4][j] = cou[3][j-1]+cou[9][j-1]+cou[0][j-1];
cou[5][j] = 0;
cou[6][j] = cou[1][j-1]+cou[7][j-1]+cou[0][j-1];
cou[7][j] = cou[2][j-1]+cou[6][j-1];
cou[8][j] = cou[1][j-1]+cou[3][j-1];
cou[9][j] = cou[2][j-1]+cou[4][j-1];
}
А уж имея массив,
ответить на второй вопрос совсем легко - это элемент массива cou[p][n-1]
, где р - начальная цифра, а n-1 – количество ходов конем
(всегда на единицу меньше длины номера, т.к. нулевая цифра не учитывается).
Для ответа на первый вопрос – надо будет организовать цикл по всем клавишам телефона, назначая их начальными…
for (int i=0; i<10; i++)
answ+=cou[i][n-1];
Не хотелось бы, но приходится ограничивать пользователя в выборе длины номера телефона, т.к. при n=26 количество вариантов такое большое, что происходит переполнение unsigned int …
Да, и пусть Вас не удивляет (не пугает), что в программе я использую одномерный массив. Элемент cou[i*m+j] - это тоже, что и cou[i][j] при условии, что j изменяется от 0 до m-1. Ведь в оперативной памяти любой многомерный массив – это все равно одномерная цепочка ячеек (битов, байтов)…
Скачивайте зашифрованный архив проекта (исходный код), а пароль ищите в вашей рассылке….
Возможно, кому-то пригодится (понадобится)
скайп-консультация… Готов ответить на вопросы…
Другие примеры на языках «C»,«C++»,«C#»
Поделиться в соц сетях: