5

Помогите решить задачу на С++

Шахматная ассоциация выдала своим сотрудникам телефоны, номера на которых можно набирать только ходом коня, причем номер не может начинаться с цифры 8 и 0

 7 8 9
 4 5 6
 1 2 3
   0

Вводится число N (1 <= N <= 100), обозначающее длину номера.
Какое количество разных номеров данной длины можно набрать?

Т.е. для N = 3 вариации могут быть такими: 1-6-7 1-6-1 2-7-6 и т.д.

5
  • форматирование текста? не, не слышал
    – teanЫЧ
    16 ноя 2012 в 10:15
  • 3
    Лошадью ходи!
    – igumnov
    16 ноя 2012 в 10:25
  • 3
    @risonyo, Согласно правилам форума, вопросы не должны сводиться к решению либо завершению учебных заданий за учащихся. Пожалуйста, уточните, что вы сделали сами и что не получилось.
    – Rules
    16 ноя 2012 в 10:59
  • да, примерно так и просчитывал таблицу возможных ходов и т.д. сложно было в виде кода реализовать
    – risonyo
    16 ноя 2012 в 12:11
  • Быстрое возведение в степень для матрицы инцидентности графа ходов решает задачу. 10 апр 2021 в 21:53

2 ответа 2

6

Задача на самом деле, если хорошо подумать, сводится к простому перебору и перемножению вариаций на разных этапах. Приблизительный алгоритм:

1) Нужно предварительно составить так называемые "таблицы возможных ходов" для каждой кнопки, например, для кнопки 1 имеем возможные ходы на 6, 6, 8 и 8, т.е на 6 и 8( две вариации ), для кнопки 2 имеем также два варианта хода: на 9 и на 7. Думаю, это понятно.

2) Вторым шагом вам необходимо поочередно от каждой кнопки ходить конем N раз( ходить по правилам составленной выше таблицы ), выводя при этом полный текущий путь от самой первой кнопки. Инкрементируя при этом определенный счетчик ходов.

Высчитывать количество вариаций ходов можно и иным способом, как уже многие поняли. Это делается банальным перемножением количества вариаций ходов от каждой кнопки.

P.S Позже, думаю, смогу продемонстрировать уже доработанный алгоритм в действии, если вы сами не сможете...

0
2

Если мне не изменяет логика, то решение должно быть таким. Старался написать максимально компактно, поэтому не во всех местах понятно идею алгоритма.

#include "iostream"
using namespace std;
int main()
{
    char can_go[10][3]={{4,6,-1},{6,8,-1},{7,9,-1},{4,8,-1},{0,3,9},{-1,-1,-1},{0,1,7},{2,6,-1},{1,3,-1},{2,4,-1}};
    int end_digits[10]={0,1,1,1,1,1,1,1,0,1},temp[10],s,n,i=0,j,l;
    for(cin>>n;i<n;i++)
      {
          for(j=s=0;j<10;s+=end_digits[j],temp[j++]=0);
          for(j=0;j<10;j++)
                for(l=(end_digits[j]?0:3);l<3;(can_go[j][l]!=-1?temp[can_go[j][l++]]+=end_digits[j]:l++));
          for(j=0;j<10;end_digits[j]=temp[j++]);
      }
    cout<<s<<endl;
    system("pause");
    return 0;
}

Условный алгоритм:

  1. Обьявление переменных. Создаётся массив can_go, строчка которого равна номерам ячеек, в которые мы можем переходить с ячейки под номером столбика (тоесть цифра, которая может идти после той, которая равна номеру столбца). Создаётся массив end_digits, который равен колличеству каждой цифры в конце номеров, созданых на данный момент (сам номер мы не запоминаем). Массив temp - временный, который будет переноситься в end_digits, переменная s - сумма (результат работы программы), i, j, l - для обхода массивов.

  2. В начале каждого шага (колличество шагов - n) обнуляем массив temp и считаем сумму s.

  3. Следующим шагом добавляем возможные номера телефонов. Добавляем их только если end_digits[j]>0, обходим каждый эллемент can_go[j] и добавляем к эллементу массива temp под номером, равным цифре номера телефона, в которую можем попасть, тоесть can_go[j][l].

  4. Переносим массив temp в end_digits.

  5. Повторяем шаги 2-4 n раз и выводим результат - s.

6
  • Это решение "в лоб". На олимпиадах такое возможно, но поскольку предъявляются требования к памяти и времени выполнения, то они зачитываются только на простых тестах. На более сложных тестах - результат не зачтется. Суть олимпиады - не решить задачу, а найти наилучшее решение. Хотя в данном случае (поскольку N <= 100) - олимпиада для школьников, возможно это решение и проканает... А что было бы, если бы N ~ 100000? Сколько бы времени выполнялось данное решение?
    – BOPOH
    17 ноя 2012 в 15:58
  • @BOPOH, я и не отрицаю, что решение "в лоб", здесь вроде как оно и требовалось :) Именно на олимпиаде намного лучше было бы попробовать решить в лоб, потом проанализировать десяток тестов и найти закономерность. Показаный тут алгоритм работает "неэкономно" в плане памяти и времени.
    – Crasher
    17 ноя 2012 в 19:38
  • А не... Я не правильно понял, че-то мне сначала показалось, что вы получаете все возможные номера и считаете их количество. Алгоритм у вас почти верный. "Почти" - не увидел где из конечного результата вычитаются суммы для 0 и 8. А потому и решение неверное. И объяснение хромает))
    – BOPOH
    17 ноя 2012 в 19:45
  • @BOPOH, в любом случае, попробовать найти закономерность стоило бы — тогда можно максимально упростить алгоритм. А насчёт 0 и 8 — спасибо, что подметили, я и забыл. Чтобы сделать невозможным начало номера с этих цифер — стоит просто изменить начальную установку массива end_digits на {0,1,1,1,1,1,1,1,0,1}. Обьяснением не особо занимался, поэтому и написал, что алгоритм "условный" :)
    – Crasher
    18 ноя 2012 в 15:21
  • @Crasher, опять не совсем правильно понял ваш алгоритм)) Когда сам решал - шел по-другому пути - добавлял цифры к началу. Решение было почти один-в-один ваше, вот только мне надо было в конце суммировать все, кроме 0 и 8, а у вас надо было исключить сразу) "Условный" алгоритм - у вас это словесное описание данной реализации. А алгоритм простой: опишу в следующем комментарии.
    – BOPOH
    18 ноя 2012 в 16:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.