Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Старый клен, старый клен, старый клен стучит в окно...

Старый клен, старый клен, старый клен стучит в окно...
Я
   Злопчинский
 
24.12.12 - 03:25
Рассмотрим задачу.
Дано:
Есть 1000 окон и 1000 человек.
1 человек приводит все окна в исходное состояние - закрывает
после этого:
2 человек меняет состояние каждого второго окна на противоположное
после этого
3 человек меняет состояние каждого третьего окна на противоположное
после этого
4 человек меняет состояние каждого четвертого окна на противоположное
и т.д. до последнего человека.
.
Требуется:
после того как все человеки выполнили действия - определить сколько окон будет закрыто/скольо открыто.
.
Задачу решили но как-то не сильно строго - четкой математической базы не подвели...
.
ДРУГАЯ ФОРМУЛИРОВКА (мне кажется, более простая): количество инверсий ячейки - это количество натуральных чисел, на которые номер ячейки делится нацело (без остатка), без учёта единицы.
.
Например, 36 делится нацело на числа 2, 3, 4, 6, 9, 12, 18, 36 (число 1 отбрасываем). Таким образом, ячейка номер 36 будет проинвертирована 8 раз, и её конечное состояние будет эквивалентно исходному (будет нуль).
.
Таким образом, нужно посчитать количество натуральных чисел, меньших 1000, которые представимы в виде квадратов других натуральных чисел. Легко увидеть, что таких чисел 31. 31^2=969, а уже 32^2=1024.
.
Итого при таким образом сформулированной задаче ответ получится:
31 нулей
969 единиц
.
но вот как-то.. мучают сомнения...
.
спасибо.
 
 
   1Сергей
 
1 - 24.12.12 - 09:22
Сомневаешься? Проверь!
   Dmitry77
 
2 - 24.12.12 - 09:33
напиши программу - всего то 2 цикла. И вывод этой ТЗ.
   napagokc
 
3 - 24.12.12 - 09:36
эмм...? Задачка же решается одним циклом на любом языке программирования. В чем сомнения-то?
   Dmitry77
 
4 - 24.12.12 - 09:37
(3) пример приведи с одним циклом. Можно на 1с.
   Serg_1960
 
5 - 24.12.12 - 09:47
(0) Один добрый человек закрыл все окна (исходное состояние).
Потом два придурка "меняют состояние" - первый из них открывает окно, а второй следом за ним закрывает это-же окно... Поднедельник, утро - не я один так дико торможу и это радует :)
   napagokc
 
6 - 24.12.12 - 10:23
const
 max = 1000;
var
 i, j: Integer;
 a: array [1..max] of boolean;
begin
 for i := 1 to max do
   a[i] := False;
 for i := 2 to max do begin
   j := 0;
   while j < max do begin
     j := j + i;
     a[j] := not a[j];
   end;
 end;
 j := 0;
 for i := 1 to max do
   if a[i] then
     Inc(j);
 ShowMessage('TRUE = '+IntToStr(j));
end;

выдает 969, (0) все правильно вычислил
   napagokc
 
7 - 24.12.12 - 10:24
только, наверное,
while j <= max do

но суть не изменилась :)
   1Сергей
 
8 - 24.12.12 - 10:25
(6) это ты называешь одним циклом?
   napagokc
 
9 - 24.12.12 - 10:27
(8) Ну, двойной цикл получился, угу :) Еще два цикла - один для инициализации, а другой для отделения уже нужного результата. Все равно задача на 5 минут
   Злопчинский
 
10 - 24.12.12 - 11:44
написать не проблема, написано уже
.
//*******************************************
Процедура Сформировать()
   
   ТЗ = СоздатьОбъект("ТаблицаЗначений");
   ТЗ.НоваяКолонка("Переключатель","Число");
   ТЗ.КоличествоСтрок(1000);
   ТЗ.Заполнить(0,1,1000,"Переключатель");
   
   Для    ы=2 по 1000
   Цикл
       Сообщить(ы);
       ыы = 0;
       Пока ыы <= (1000-ы)
       Цикл
           ыы = ыы+ы;
           ТЗ.ПолучитьСтрокуПоНомеру(ыы);
           ТЗ.Переключатель = 1-ТЗ.Переключатель;
       КонецЦикла;    
   КонецЦикла;
   
   Сообщить(ТЗ.Итог("Переключатель"));    
   ТЗ.ВидимостьКолонки("НомерСтроки",1);
   ТЗ.ВыбратьСтроку(,);
КонецПроцедуры
 
 Рекламное место пустует
   Злопчинский
 
11 - 24.12.12 - 11:45
решить нужно математически. решение тупое в лоб перебором - это не правильно.
   1Сергей
 
12 - 24.12.12 - 11:54
(11) решение ведь в (0). Не?
   Злопчинский
 
13 - 24.12.12 - 11:55
(12) не знаю, как-то не удалось его сложить связно...
   lepesha
 
14 - 24.12.12 - 12:14
(0) Вы там теорему Лагранжа пытаетесь опровергнуть?
"Всякое натуральное число можно представить в виде суммы четырех квадратов целых чисел."
wiki:Теорема_Лагранжа_о_сумме_четырёх_квадратов
Так что "количество натуральных чисел, меньших 1000, которые представимы в виде квадратов других натуральных чисел" таки равно тысяче :)
   Злопчинский
 
15 - 24.12.12 - 14:32
(14) ненене... так высоко мы не замахиваемся! надо всего лишь решить задачу в сабже
   Жан Пердежон
 
16 - 24.12.12 - 15:10
31^2=961
   Злопчинский
 
17 - 24.12.12 - 15:12
(16) до этого мы и сами как-то дошли, но вот ОБОСНОВАТь....
   Deon
 
18 - 24.12.12 - 15:15
(10) И почему все тру-программеры обожают переменные ыы, жж, гг, ёё...
   НикДляЗапросов
 
19 - 24.12.12 - 15:18
Ну я так понимаю через пределы решается
   acsent
 
20 - 24.12.12 - 15:20
Не понял перехода:
Таким образом, нужно посчитать количество натуральных чисел, меньших 1000, которые представимы в виде квадратов других натуральных чисел. Легко увидеть, что таких чисел 31. 31^2=969, а уже 32^2=1024.
   sda553
 
21 - 24.12.12 - 15:41
Каждое число есть разложение на простые числа, такое разложение единственное:
Например 1000 = 2*2*2*5*5*5
Очевидно что количество инверсий, равно количеству различных чисел которое можно составить из 6-ти этих. Т.е. для 1000 это будет
2 (каждое второе окно)
5 (каждое пятое)
2*2 (кажде 4-е окно)
2*5
5*5
2*2*2
2*2*5
2*5*5
5*5*5
2*2*2*5
2*2*5*5
2*5*5*5
2*2*2*5*5
2*2*5*5*5
2*2*2*5*5*5

Итого 15 инверсий.
Т.к. разложение единственное, то для решения задачи достаточно сделать 10 ячеек (2^10>1000, так что достаточно)
и начинать ставить в этих 10-ти ячейках все возможные сочетания простых чисел от 2 до 499 (таких чисел 95), естественно в возрастающем порядке, чтобы избежать повторов.
При этом, правда получаться числа и >1000.
   lepesha
 
22 - 24.12.12 - 17:48
Почему бы не посчитать количество чисел от 2 до 1000, имеющих четное количество делителей без остатка в интервале от 2 до 1000?
   Злопчинский
 
23 - 24.12.12 - 18:10
(20) если не понял - не заморачивайся - это размышления так сказать в качестве дежурного бреда
   Злопчинский
 
24 - 24.12.12 - 18:10
(21) количество ячеек в задаче ЗАДАНО ИСХОДНО.
   Злопчинский
 
25 - 24.12.12 - 18:12
(21) 15 инверсий - ничего не дает. сколько при твоем решении будет открытх окон и скольо закрытых из 1000..?
   sda553
 
26 - 24.12.12 - 22:11
(25) Это дает что тысячное окно будет открыто и закрыто 15 раз
(24) Нет, не задано, ты меня не понял, скорее всего.
   Злопчинский
 
27 - 24.12.12 - 22:57
(26) количество ОКОН - задано исходно. Важно не сколько раз открыто/закрыто будет окно. а в конечном итоге - скольо окон будет закрыто/открыто ИЗ ЗАДАННОГО ИСХОДНОГО КОЛИЧЕСТВА.
.
количество людей = количеству окон.
   sda553
 
28 - 24.12.12 - 23:07
(27) Я же говорю, что ты меня не понял. Ячейки в моем решении <> окна
   sda553
 
29 - 24.12.12 - 23:09
(27) Завтра выложу какое нибудь законченное решение, попробую
   Юрий Лазаренко
 
30 - 24.12.12 - 23:10
(0) Мне кажется или это драконова кривая? или как там она называется.
   sda553
 
31 - 25.12.12 - 00:08
Блин, все резко упрощается.
Итак
1. Каждое окно инвертируется столько раз, сколько у его номера по счету существует различных (не обязательно простых) делителей.
например у окна 10, делители 1,2,5,10 а значит оно инвертируется 4 раза.
Теперь обратим внимание. Раз число 10 делится на 2, то логично, что оно делится и на 10/2, т.е. на 5.
Или вообщем если число n делится на m, то оно делится и на n/m.

А значит, у любого целого n числа всегда ЧЕТНОЕ число делителей, так как у каждого делителя m существует делитель n/m, кроме тех чисел у которых есть такой делитель m, что n/m равно самому m.
Рассмотрим внимательнее теперь числа n для которых существует m, что n/m=m,  
очевидно, что n=m^2,  а знчит эти числа, квадраты натуральных чисел. А у них НЕЧЕТНОЕ число инверсий.
Ну а дальше все элементарно
   lepesha
 
32 - 25.12.12 - 01:21
(31) "Или вообщем если число n делится на m, то оно делится и на n/m." - и что вам даст n/n*m? И как вы пришли к выводу о четном числе делителей? Дирихле с вами не согласен :)
   Злопчинский
 
33 - 25.12.12 - 01:39
наблюдаю.
кто даст законченный вывод?
 
 
   sda553
 
34 - 25.12.12 - 06:55
(32) как раз первая часть вашего предложения дает то, что во второй части приложения.
Если для каждого ботинка есть парный ботинок, то мы имеем четное число ботинков, так?
Меняем слова:
Если для каждого делителя m есть парный делитель n/m, то мы имеем четное число делителей.
   lepesha
 
35 - 25.12.12 - 09:05
(34) Попробую объяснить проще - перемножьте любое нечетное количество членов ряда простых чисел.
   sda553
 
36 - 25.12.12 - 10:10
(35)
Ок, берем нечетное количество простых чисел, например 2,3,5
Перемножаем, получаем число 2*3*5=30
Теперь посмотрим сколько делителей у числа 30, а они вот
1,2,3,5,6,10,15,30.
Т.е. восемь делителей.
В чем вопрос?
   lepesha
 
37 - 25.12.12 - 11:05
(36) Пробуйте еще.
   lepesha
 
38 - 25.12.12 - 11:13
Например с числами 4, 9, 16, 25.
   sda553
 
39 - 25.12.12 - 11:35
(38) у них будет нечетное число делителей.
Смотри внимательно (31)
У любого целого числа n всегда четное число делителей,..... КРОМЕ ТЕХ ЧИСЕЛ....
Теперь я все решение (31) разжевал? Или еще вопросы
   lepesha
 
40 - 25.12.12 - 13:38
(39) Смотрел невнимательно, поэтому нечетное количество делителей у полных квадратов в формулировке не увидел. Теперь все ОК :)
   Злопчинский
 
41 - 26.12.12 - 18:04
(39) Есть "или еще вопросы". Приведите конкретное решение для варианта 1000 окон и 1000 людей.
.
спсб!
   sda553
 
42 - 27.12.12 - 12:45
(41) С учетом (31) все окна порядковые номера которых являются квадратами будут закрыты.
Это окна с номерами: 1^2; 2^2; 3^2; ...., 31^2
Остальные открыты.
Значит 31 закрытое и 969 открытых
   Vladal
 
43 - 27.12.12 - 13:20
(10) [code]Для    ы=2[/code]

Я думал, что один такой, когда пишу [code]Для ъ=2[/code]
   Vladal
 
44 - 27.12.12 - 13:23
(18) Так не ошибешься)))
В каком-то учебнике по программированию писали стандарт по переменным, что вспомнил: для счетчикв циклов использовать переменные с именем i,j,k,l, для произвольных целых - a,b
Точно уже не помню.
   Undefined vs NULL
 
45 - 29.12.12 - 09:48
решение в (31), а я в отпуске ))


Список тем форума
Рекламное место пустует  Рекламное место пустует
Читай всё полезное и впитывай, а нападки игнорируй. Здесь так принято. aka AMIGO
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует