Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Задача про коробки от Гугла как реализовать
Ответ
 
Опции темы Опции просмотра
  (#46 (permalink)) Старый
winamp winamp вне форума
Member
 
Сообщений: 262
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.08.2008
По умолчанию 11.11.2008, 12:34

Коробочка с номером m будет открытой, если число m имеет чётное кол-во натуральных делителей (кроме 1)

Таким образом, ответ равен сумме произведений натуральных чисел a1*...*ak, где
k-чётное
1<a1,..,ak<=N
a1*..*ak<=N

Если бы "по каждой четвертой открытой", то можно было бы(наверное)
вывести формулу. Поэтому мне кажется, что условия задачи кто-то перепутал.
Ответить с цитированием
  (#47 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 11.11.2008, 12:47

Цитата:
Коробочка с номером m будет открытой, если число m имеет чётное кол-во натуральных делителей (кроме 1)
Да, именно так, и это здесь уже написано выше - там же, где приведено решение.

Цитата:
Таким образом, ответ равен сумме произведений натуральных чисел a1*...*ak, где
k-чётное
1<a1,..,ak<=N
a1*..*ak<=N
Не сумме, а их количеству. См. то, что Вы только что написали сами (выделено жирным шрифтом). И это количество посчитано выше - в моем решении.
Цитата:
Если бы "по каждой четвертой открытой", то можно было бы(наверное) вывести формулу. Поэтому мне кажется, что условия задачи кто-то перепутал.
Нет, это Вы немножко что-то недопоняли (см. выше, что именно).
Ответить с цитированием
  (#48 (permalink)) Старый
winamp winamp вне форума
Member
 
Сообщений: 262
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.08.2008
По умолчанию 11.11.2008, 14:00

Цитата:
Не сумме, а их количеству. См. то, что Вы только что написали сами (выделено жирным шрифтом). И это количество посчитано выше - в моем решении.
да, опечатка вышла.

Однако ваша фраза:
Цитата:
Если N не является полным квадратом, то, наоборот, закрытой (т.к. в этом случае число делителей, отличных от 1, нечетно).
требует доказательств.
Ответить с цитированием
Ads
  (#49 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 11.11.2008, 17:09

Если перечитать ветку, нетрудно увидеть, что там уже приведено даже два доказательства - формальное (через разложение на простые множители) и наглядное
Ответить с цитированием
  (#50 (permalink)) Старый
winamp winamp вне форума
Member
 
Сообщений: 262
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.08.2008
По умолчанию 12.11.2008, 09:48

Цитата:
Если перечитать ветку, нетрудно увидеть, что там уже приведено даже два доказательства - формальное (через разложение на простые множители) и наглядное
вы так и не доказали:
Цитата:
Каждый несобственный делитель всегда появляется в паре с другим: N = a * b
Хотя ,вы правы, тут доказывать "нечего".
Ответить с цитированием
Ads.
  (#51 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 12.11.2008, 15:22

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

N = P1^K1 * P2^K2 * ... * Pm^Km.

Тогда общее число делителей числа N равно:

(K1 + 1) * (K2 + 1) * ... * (Km + 1).

Это, надеюсь, понятно - факт элементарный. Иначе дальше и говорить не о чем.
Заметим, что число N является полным квадратом тогда и только тогда, когда все Ki - четные. Это следует из основной теоремы арифметики.
(указание: Пусть N = X^2. Как связаны разложения на простые множители чисел N и X?).

Итак, пусть N не является полным квадратом. Тогда хотя бы одно из чисел Ki является нечетным. Значит общее количество делителей числа N, равное, как написано выше (K1 + 1) * (K2 + 1) * ... * (Km + 1), является четным. Один из делителей - единица. Вычитаем 1, получаем, что общее количество делителей числа N, отличных от единицы, нечетно.
Операция "открыть или закрыть" (ровно одно из этих действий) применяется к коробке при s-м проходе в точности тогда, когда s является делителем номера этой коробки. Пусть у коробки номер не является полным квадратом. Изначально коробка открытая. Считаем по делителям: первый раз попался делитель - закрываем (раз), второй раз попался делитель - открываем (два), третий раз - закрываем (три) и т.д. Операция применяется нечетное количество раз, следовательно, в результате коробка будет закрытой.
Ответить с цитированием
  (#52 (permalink)) Старый
winamp winamp вне форума
Member
 
Сообщений: 262
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.08.2008
По умолчанию 13.11.2008, 16:48

Всё, закругляться надо.
Ответить с цитированием
  (#53 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 13.11.2008, 19:52

Доказательство того факта, что нечетное число нетривиальных делителей имеет только полный квадрат "наглядным" способом тоже вполне строгое.

Нетрудно видеть, что все нетривиальные делители числа N попарно соответствуют друг другу исходя из соотношения a * b = N
При этом:
- каждый делитель входит в одну и только одну пару => имеем разбиение на непересекающиеся классы;
- если N не является полным квадратом, все пары состоят из различных чисел => общее число четно;
- если N является полным квадратом, существует одно и только одно число, составляющее пару самому себе => общее число нечетно.


Цитата:
Всё, закругляться надо.
Этому ответу было так одиноко на этой пустой странице..
Ответить с цитированием
  (#54 (permalink)) Старый
winamp winamp вне форума
Member
 
Сообщений: 262
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.08.2008
По умолчанию 14.11.2008, 09:37

-Это всё замечательно.

Давайте ещё пару раз, на бис!!!
Ответить с цитированием
  (#55 (permalink)) Старый
fetfrumos fetfrumos вне форума
Member
 
Сообщений: 26
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 28.11.2008
По умолчанию 01.12.2008, 23:31

pomoemu vse prosto esli chetnoe kolichestvo,korobok to budet odinakovoe kolichestvo otkrytzh i zakrytyh,esli ne chetnoe to otkrytyh budet na odin menshe(snachala ih bolshe,a potom otkrytee zakryvautsa,vse menyaetsa s tochnostu do oborot)...vot
Ответить с цитированием
  (#56 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 02.12.2008, 13:24


Знаете, что - можно поступить очень просто.
Вот пусть коробок всего 10.
Приведите нам здесь, пожалуйста, результаты каждого из десяти проходов.
Ну например, путь открытая коробка обозначается 0, а закрытая 1, или как Вам угодно. Что получится?
Ответить с цитированием
  (#57 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 03.12.2008, 00:04

Цитата:
Что получится?
Некто Макс Чубин сделал на флеше наглядное решение данной задачи.
Ответить с цитированием
  (#58 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.12.2008, 14:54

Вовремя
Симпатично так сделано.

P.S. (можно сказать, отвлеченно, to Alexiski & etc). Иногда возникает ощущение, что ферматисты бывают не только у великой теоремы Ферма.
Ответить с цитированием
  (#59 (permalink)) Старый
marktven marktven вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 20.11.2010
По умолчанию 20.11.2010, 20:09

Где же они такие задачи берут...
не догадался...
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите, задача по прологу, срочно...задача с высказываниями 4ixOn Prolog 6 10.07.2011 23:29
Помогите, задача по прологу, срочно...задача о станках 4ixOn Prolog 3 09.07.2011 22:48
Формально-логическая задача как ее реализовать Амелия Lisp 0 19.05.2011 21:46
Задача по MPI 45$ Naikon1988 Задания за деньги 2 22.12.2010 18:12
Не могу зайти на сайты Гугла. Katrina_ Любые вопросы от новичков 24 11.12.2010 22:46
Как откоючить пользовательский поиск Гугла? chocogel Любые вопросы от новичков 1 21.12.2008 12:49
OpenGL как сделать стенки коробки прозрачными imported_Nikss Delphi 3 18.09.2007 17:52
Приколы гугла gromozeka Юмор 6 30.05.2006 12:28
Задача про козу, капусту и волка как реализовать MP Lisp 3 25.05.2006 01:04
задача на Си int33 Задания за деньги 1 14.04.2006 17:53
Задача: Последовательность как реализовать oleg88kpuk Алгоритмы 0 09.03.2005 21:10
А,В,С- задача про них!! Anonymous Вопросы начинающих программистов 0 08.01.2004 22:22



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов