2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Найти количество чисел, сумма цифр которых делится на 11...
Сообщение20.11.2011, 00:01 


13/11/11
574
СПб
У меня есть несколько заданий, над которыми уже долго бьюсь, но левела видать не хватает, тяготят долгими зимними вечерами..

Одна: найти количество 4хзначных чисел, сумма цифр которых делится на 11.
И как я её не пробовал.. максимум, что придумал - это если зафиксировать одну цифру, то сумма остальных 3х будет равна чему-то конкретному, на эту сумму есть ограничения, её можно тоже разбить на какие-то суммы с ограничениями.. и потом всё это перебрать\скомбинировать. Нужный ответ (818, кажется, программой проверял) так и не получился. Знаю, что можно как-то вычетами..

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 00:08 
Заслуженный участник


09/09/10
3729
Unconnected в сообщении #505507 писал(а):
найти количество 4хзначных чисел, сумма которых делится на 11.

Сумма цифр, наверное? Максимально возможная сумма цифр у 4-значного числа равна 36. Значит, вашу задачу можно разбить на три подзадачи: все четырехзначные числа, сумма цифр которых равна 11, 22 или 33. Далее, пожалуй, действительно можно фиксировать по очереди цифры и считать. Нудно, но надежно. Возможно, есть способ поостроумнее.

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 00:13 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Да что там фиксировать. В лоб перебрать - и только.
Вот если бы цифр было хотя бы этак 12, то там - - -

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 00:21 


13/11/11
574
СПб
Да, сумма цифр.
Кажется, это более чем нудно, очень много перебирать (у меня так выходило, по крайней мере).

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 00:53 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Код:
foreach(1000..9999){$n++ if(eval join"+",split//)%11==0} print $n
Да, действительно нудно (думал, уложусь символов в 50, да где там!..)

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 01:22 


13/11/11
574
СПб
Ну так я тоже умею)

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 06:59 
Заслуженный участник


08/04/08
8562
Рекуррентная формула:
$N(x_1+\dots+x_k=n) = \sum\limits_{x_k=0}^9 N(x_1+\dots+x_{k-1}=n-x_k)$.
Используя ее, выведите формулу в общем виде для $k=4$ (ну или так подсчитайте), используя формулу для $k=1$: $N(x_1=n)=[n \leqslant 9]$.

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 14:56 


13/11/11
574
СПб
А что значит N в этой формуле?

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 14:59 
Аватара пользователя


12/01/11
1320
Москва
количество $k$-значных чисел с суммой цифр $n$

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 15:27 


26/08/11
2108
Можно поделить сумму на 2 пары. Первые 2 и последние 2. Распределение суммы для 2 цифр елементарно
Код:
00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18
01,02,03,04,05,06,07,08,09,10,09,08,07,06,05,04,03,02,01
И там как получить 11,22,33. Неприятно, но решимо.

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 16:47 
Заслуженный участник


08/04/08
8562
Unconnected в сообщении #505667 писал(а):
А что значит N в этой формуле?

$N(F(x_1,\dots ,x_k)=0)$ - число решений уравнения $F(x_1,\dots ,x_k)=0$. Очень удобная штука.

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 16:56 
Заслуженный участник


09/09/10
3729

(Оффтоп)

Вообще говоря, смахивает на задачу динамического программирования...

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение20.11.2011, 17:14 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории

(Оффтоп)

да, похоже. но
ИСН в сообщении #505509 писал(а):
Вот если бы цифр было хотя бы этак 12, то там - - -

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение26.11.2011, 01:23 


13/11/11
574
СПб
Цитата:
Используя ее, выведите формулу в общем виде

А можно указание, с чего это начинать? Как бы смысл понял, но неужели для этого большого перебора есть просто эквивалентная формула?

 Профиль  
                  
 
 Re: Несколько задач АТЧ
Сообщение26.11.2011, 08:12 
Заслуженный участник


08/04/08
8562
Unconnected в сообщении #508169 писал(а):
А можно указание, с чего это начинать?
Ну вот так и начинайте:
$k=2$:
$N(x_1+x_2=n)= \sum\limits_{x_2=0}^9 N(x_1=n-x_2)= \sum\limits_{x_2=0}^9 [0 \leqslant n-x_2 \leqslant 9] = $
$[0 \leqslant n \leqslant 9]\sum\limits_{x_2=0}^9 [x_2 \leqslant n][x_2 \geqslant n-9]+[10 \leqslant n \leqslant 18]\sum\limits_{x_2=0}^9 [x_2 \leqslant n][x_2 \geqslant n-9]=$
$[0 \leqslant n \leqslant 9]\sum\limits_{x_2=0}^9 [x_2 \leqslant n]+[10 \leqslant n \leqslant 18]\sum\limits_{x_2=0}^9 [x_2 \geqslant n-9]=$
$[0 \leqslant n \leqslant 9]\sum\limits_{x_2=0}^n 1 +[10 \leqslant n \leqslant 18]\sum\limits_{x_2=n-9}^9 1 = $
$[0 \leqslant n \leqslant 9](n+1) +[10 \leqslant n \leqslant 18](9-(n-9)+1)$

(в формуле выше исправил индекс суммирования)

Unconnected в сообщении #508169 писал(а):
Как бы смысл понял, но неужели для этого большого перебора есть просто эквивалентная формула?
Ну да, просто ее выводить трудно.
Я, кстати, не утверждаю, что у меня самое простое решение, наверняка нет. Просто так можно решать. У меня не красиво получается

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 47 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group