Автор Тема: Найти количество шестизначных чисел  (Прочитано 359 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн johnybrsosoqlol

  • Пользователь
  • Сообщений: 2
  • Поблагодарили: 1 раз(а)
    • Просмотр профиля
Найти количество шестизначных чисел
« : Октябрь 25, 2017, 05:35:11 pm »
Найти, сколько шестизначных чисел в троичной системе счисления не содержат рядом стоящих нулей?

Помогите решить, пожалуйста, скоро модуль, а препод такое не объяснял
 
Сказали спасибо: Байт

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Комбинаторика
« Ответ #1 : Октябрь 25, 2017, 09:32:49 pm »
Найти, сколько шестизначных чисел в троичной системе счисления не содержат рядом стоящих нулей?
Замечание. Каждую задачу следует размещать в отдельной теме. А то мы с вами запутаемся.
Тут можно предложить рекурсивную схему.
Пусть A(k), B(k) - количество последовательностей из 0,1,2 не содержащие 2-х нулей подряд длины k
Но A(k) - заканчивающиеся на 0, B(k) - на 1 и 2
A(k+1) = B(k) + 2*A(k)
B(k+1) = 2*A(k) + 2*B(k)
A(1) = 1
B(1) = 2
A(2) = 2 + 2*1 = 4
B(2) = 2*1 +2*2 = 6
И так далее.
Нас интересует 2*(A(5) + B(5))
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Найти количество шестизначных чисел
« Ответ #2 : Октябрь 25, 2017, 09:40:08 pm »
Я тут ошибся в определении A(k+1) = B(k)
Исправления на другом форуме.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5048
  • Поблагодарили: 1576 раз(а)
    • Просмотр профиля
Re: Найти количество шестизначных чисел
« Ответ #3 : Октябрь 25, 2017, 10:01:27 pm »
Замечание. Каждую задачу следует размещать в отдельной теме. А то мы с вами запутаемся.

Байт, спасибо. Отделил задачу.
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Найти количество шестизначных чисел
« Ответ #4 : Октябрь 27, 2017, 10:28:10 pm »
Рассмотрение этой задачи оказалось весьма плодотворным. В итоге ее решение, наивно изложенное в ответе #1, удалось оформить в виде рекурсивного алгоритма, покрывающего некий класс похожих (что не всегда очевидно!) задач. При этом эффективность - чудовищная! Вместо экспоненты (тупой перебор) мы имеем O(n). Не думаю, что мы с вами тут открыли Америку и пора подавать заявку на Филдсовскую премию:D
Но то, что мы сами что-то придумали - приятно. Даже если это и велосипед. :)
Поэтому-то я и выражаю доступным мне способом благодарность ТС.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Найти количество шестизначных чисел
« Ответ #5 : Октябрь 27, 2017, 10:40:55 pm »
Более того, моему коллеге, значительно лучше меня владеющему математическими аппаратами, удалось представить мои наивные соображения в матричном виде.
Это все в подтверждение слов Анны Андреевны - "Когда б вы знали, из какого сора рождаются стихи!" :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Re: Найти количество шестизначных чисел
« Ответ #6 : Декабрь 05, 2017, 10:27:59 pm »
В самом деле, не прошло и года, как выяснилось, что у задач подобного типа есть и решение в виде конечной формулы. Только она почему-то с корнями получается. Типа формулы Бине. :) Но все - сопряженное. Так что первую проверку "на вшивость" (на "полтора землекопа") она проходят.
Если кто заинтересовался - милости прошу :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin