Автор |
Сообщение |
atakga
|
Заголовок сообщения: Натуральное число Добавлено: 22 мар 2015, 13:01 |
|
Зарегистрирован: 20 дек 2013, 17:51 Сообщений: 118 Откуда: Занзибар
|
Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее!
|
|
|
|
|
|
|
michel
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 16:29 |
|
Зарегистрирован: 17 дек 2010, 20:02 Сообщений: 1678
|
atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много).
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 17:02 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
michel писал(а): atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много). b(0) = b(1) = 1. n >=0 --> b(2n+1) = ????? b(2n+2) = ????? Потом воспользоваться этой рекурсией и получить результат за 11 шагов. Hint. Чему равно a0 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы. А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея.
|
|
|
|
|
OlG
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 18:33 |
|
Зарегистрирован: 09 апр 2011, 14:49 Сообщений: 6791 Откуда: Москва
|
alex123 писал(а): michel писал(а): atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много). b(0) = b(1) = 1. n >=0 --> b(2n+1) = ????? b(2n+2) = ????? Потом воспользоваться этой рекурсией и получить результат за 11 шагов. Hint. Чему равно a0 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы. А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея. `b(1997)=872`.
_________________ Никуда не тороплюсь!
Последний раз редактировалось OlG 22 мар 2015, 18:38, всего редактировалось 1 раз.
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 18:36 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
OlG писал(а): `b(1997)=871`. Нет, 38.
|
|
|
|
|
OlG
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 20:19 |
|
Зарегистрирован: 09 апр 2011, 14:49 Сообщений: 6791 Откуда: Москва
|
alex123 писал(а): Нет, 38. Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается (недолгим перебором) еще 37 вариантов представления.
_________________ Никуда не тороплюсь!
|
|
|
|
|
atakga
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 21:35 |
|
Зарегистрирован: 20 дек 2013, 17:51 Сообщений: 118 Откуда: Занзибар
|
Спасибо всем откликнувшимся! Ниже привожу решение этой задачи. Хотел найти более простую решение задачи с помощью посетителей форума. Принимая во внимание какое значение может получить `a_(0)` получим: `b(2n+1) = b(n)` и `b(2n) = b(n) + b(n-1)`. Для `n=1997` получим `b(1997) = b(998) = b(499) + b(498) = 2b(249) + b(248) = 2b(124) + b(248)` `(1)` `b(62) = b(31) + b(30), ( b(31) = b(15) = b(7) = b(3) = b(1) = 1 ) ==> b(62) = b(30) + 1` `b(124) = b(62) + b(61) = b(62) + b(30) = 2b(30) + 1` `(2)` `b(248) = (2b(30) + 1) + b(123) = 3b(30) + 1` `(3)` Подставляя `(2)`и `(3)` в `(1)` получим: `b(1997) = (4b(30) + 2) + (3b(30) + 1) = 7b(30) + 3` `b(30) = b(15) + b(14) = 1 + b(14) = 1 + b(7) + b(6) = 2 + b(6) = 2 + b(3) + b(2) = 3 + b(2) = 5` Отсюда получим `b(1997) = 7 x 5 + 3 = 38`.
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 22:22 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
OlG писал(а): alex123 писал(а): Нет, 38. Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается (недолгим перебором) еще 37 вариантов представления. Так предъявите? И докажите, что 39-го варианта нет.
|
|
|
|
|
OlG
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 22:46 |
|
Зарегистрирован: 09 апр 2011, 14:49 Сообщений: 6791 Откуда: Москва
|
alex123 писал(а): OlG писал(а): alex123 писал(а): Нет, 38. Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается (недолгим перебором) еще 37 вариантов представления. Так предъявите? И докажите, что 39-го варианта нет. `11111001101` `11111001021` `11111000221` `11110201101` `11110201021` `11110200221` `11110121101` `11110121021` `11110120221` `11110112221...` `02222112221`.
_________________ Никуда не тороплюсь!
|
|
|
|
|
alex123
|
Заголовок сообщения: Re: Натуральное число Добавлено: 22 мар 2015, 23:04 |
|
Зарегистрирован: 16 фев 2011, 14:13 Сообщений: 1940
|
OlG писал(а): `11111001101`
`11111001021`
`11111000221`
`11110201101`
`11110201021`
`11110200221`
`11110121101`
`11110121021`
`11110120221`
`11110112221...`
`02222112221`.
Тут пока явно меньше, чем 38
|
|
|
|
|
|
|
|