Программа на С++ (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#»




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...

Сайт помощи студентам по программированию и информатике

Program code