Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Задача про коробки от Гугла как реализовать
Ответ
 
Опции темы Опции просмотра
  (#16 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 18.10.2008, 20:29

Alexiski, мне кажется, что это можно показать попроще.

N (>1) является полным квадратом <=> в его разложении на простые множители все степени являются четными (это очевидно) <=> общее количество различных делителей N нечетно <=> N имеет четное количество делителей, отличных от 1.

Остается применить индукцию по N. Для маленьких значений N можно проверить в лоб. Предположим, что для N-1 все верно. Проверим для N. Последний, N-й проход на состояния (открытая-закрытая) предыдущих коробок не влияет, поэтому для них все верно (если номер - полный квадрат, то она открытая, а если нет, то закрытая).
Если N - полный квадрат, то количество делителей, больших 1, четно, изначально коробка открытая, поэтому операций закрыть-открыть будет проделано четное число, так что коробка в результате будет открытой.
Если N не является полным квадратом, то, наоборот, закрытой (т.к. в этом случае число делителей, отличных от 1, нечетно).
Ответить с цитированием
  (#17 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 18.10.2008, 20:35

Я сразу допёр до квадратов. Но не до доказательства.
Ответить с цитированием
  (#18 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 18.10.2008, 20:35

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

Цитата:
в его разложении на простые множители все степени являются четными (это очевидно) <=> общее количество различных делителей N нечетно
Вот это наименее очевидно. Собственно, в конце концов я так и сделал.
Но мне кажется, что с разбиением делителей на пары то же самое получается проще и нагляднее.
Ответить с цитированием
  (#20 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 19.10.2008, 00:23

Цитата:
в его разложении на простые множители все степени являются четными (это очевидно) <=> общее количество различных делителей N нечетно
Вот это наименее очевидно. Собственно, в конце концов я так и сделал.
Но мне кажется, что с разбиением делителей на пары то же самое получается проще и нагляднее.
Ответить с цитированием
Ads.
  (#21 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 19.10.2008, 17:36

Ну, например, пусть разложение на простые множители имеет вид:

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

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

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

Т.к. все Ki - четные (иначе N не было бы полным квадратом), то выше написано произведение нечетных чисел, а оно всегда является нечетным.
Ответить с цитированием
  (#22 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 19.10.2008, 17:36

Ну, например, пусть разложение на простые множители имеет вид:

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

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

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

Т.к. все Ki - четные (иначе N не было бы полным квадратом), то выше написано произведение нечетных чисел, а оно всегда является нечетным.
Ответить с цитированием
  (#23 (permalink)) Старый
Guzilas Guzilas вне форума
Member
 
Сообщений: 80
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2008
По умолчанию 01.11.2008, 09:02

Задача на сообразительность а не на знания математики
Ответить с цитированием
  (#24 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 01.11.2008, 19:32

Математика-то здесь школьная, и ее знание не поможет без сообразительности.

Ну и как Вы решите эту задачу без математики?
Ответить с цитированием
Ads
  (#25 (permalink)) Старый
Guzilas Guzilas вне форума
Member
 
Сообщений: 80
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2008
По умолчанию 02.11.2008, 00:56

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

Слово "провокация"? В связи с такой-то задачей?
Просто сказали бы честно, что Вы бы эту задачу не решили, и все. Ничего такого в этом нет.
А из знания математики здесь нужен только факт о разложении натуральных чисел на простые множители, известный всем, причастным к программированию. Все остальное - чистая сообразительность.
Ответить с цитированием
  (#27 (permalink)) Старый
just_vladimir just_vladimir вне форума
Member
 
Сообщений: 420
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2006
По умолчанию 02.11.2008, 15:25

Про эту задачку как то писали на хабре, там ещё помимо самой задачки было рассказано при каких условиях её получил соискатель работы в Google
Ответить с цитированием
  (#28 (permalink)) Старый
Guzilas Guzilas вне форума
Member
 
Сообщений: 80
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2008
По умолчанию 06.11.2008, 02:49

Цитата:
Слово "провокация"? В связи с такой-то задачей?
Просто сказали бы честно, что Вы бы эту задачу не решили, и все. Ничего такого в этом нет.
А из знания математики здесь нужен только факт о разложении натуральных чисел на простые множители, известный всем, причастным к программированию. Все остальное - чистая сообразительность.
А вы уверены в том чего не знаете !
Ответить с цитированием
  (#29 (permalink)) Старый
winamp winamp вне форума
Member
 
Сообщений: 262
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.08.2008
По умолчанию 06.11.2008, 09:41

Цитата:
Есть N коробок. Все они открыты. Человек проходит и закрывает каждую вторую коробку. Затем проходит по каждой третей коробки, если она открыта закрывает, если закрыта открывает. Потом по каждой четвёртой и так до N. Сколько коробок останутся открытыми после всех этих действий?
-в данной формулировке ответ очевиден.
И не каких квадратов и разложений. Ведь не написано "Потом по каждой четвёртой открытой" ))
Ответить с цитированием
  (#30 (permalink)) Старый
Guzilas Guzilas вне форума
Member
 
Сообщений: 80
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.10.2008
По умолчанию 06.11.2008, 10:23

Надо поменьше между строк читать, тогда все будет просто и понятно
Ответить с цитированием
Ответ

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

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

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 - компьютерный форум и программирование, форум программистов