Вход | Регистрация
 
1С:Предприятие :: 1С:Предприятие 8 общая

Задачка по программированию/математике

↓ [Волшебник, 30.10.19 - 09:36]
Задачка по программированию/математике
Я
   fisher
 
29.10.19 - 17:41
Понравилась задачка по программированию/математике. Из тех, что первокурсникам-программистам дают. Нашел элегантное решение и радуюсь. Может, надо было в программисты идти? :))
"Напишите функцию, которая найдет самое маленькое число, которое делится нацело на все числа от 1 до N (N<40, вводится пользователем)"
 
 
   mikecool
 
1 - 29.10.19 - 17:43
я таких мозгодробилок(для меня иначе и не назовешь) на питоне штук 40 нарешал )
   fisher
 
2 - 29.10.19 - 17:44
(1) Млдц!
   МимохожийОднако
 
3 - 29.10.19 - 17:44
(0) Я за тебя тоже радуюсь.
   fisher
 
4 - 29.10.19 - 17:47
(3) Дык! За такого красавчика грех не порадоваться! Затем и поделился!
   aleks_default
 
5 - 29.10.19 - 17:48
А мне грустно, потому что вспоминил школу и уроки информатики в 5-ом классе...
   hhhh
 
6 - 29.10.19 - 17:49
(4) ну, выкладывай, потестируем
   dmt
 
7 - 29.10.19 - 17:50
(0)
> Может, надо было в программисты идти?
поздно ((
   fisher
 
8 - 29.10.19 - 17:50
(6) Шиш тебе! Сам любоваться буду!
Хочешь и себе такую лапочку - сам пиши!
(7) Отож :(
   hhhh
 
9 - 29.10.19 - 17:54
(8) ок. не хочу я эту лапочку. Просто можно было проверить. Наверняка какую-то бредятину ведь написал, и радуешься.
   fisher
 
10 - 29.10.19 - 17:56
Чем меня всегда раздражали программные реализации математических концепций - так это если нет соответствующей математической базы, то хрена лысого ты разберешься, как эта программа работает. Ну т.е. типа угадал все буквы - а слова назвать не можешь.
Тут прелесть в том, что математическая база, как было правильно замечено, укладывается в школьную программу. И формулировка задачи очень простая.
   Креатив
 
11 - 29.10.19 - 17:56
(0)Так вроде всё просто.
r := n;
для ш := 2 до n-1 цикл
 Если r mod ш <> 0 То
   r := r * ш;
 КонецЕсли;
КонецЦикла;
За смесь языком простите.
   hhhh
 
12 - 29.10.19 - 17:59
(10) самое простейшее решение, нашел за одну минуту
Массив = Новый Массив;
Массив.Добавить(1);
Массив.Добавить(2);
Массив.Добавить(6);
Массив.Добавить(12);
Массив.Добавить(60);

...

Возврат Массив[N-1];
   pechkin
 
13 - 29.10.19 - 18:00
это же НОК.
НОК = П / НОД
   pechkin
 
14 - 29.10.19 - 18:02
НОД находится алгоритмом Эвклида
   fisher
 
15 - 29.10.19 - 18:02
Для проверки: для N = 10 ответ 2520
   fisher
 
16 - 29.10.19 - 18:03
(13) Молодец! Только если в лоб через НОД решать для нескольких чисел, решение будет не шибко элегантным.
   hhhh
 
17 - 29.10.19 - 18:08
(15) а если N = 40 000 000, сколько получается?
   bolobol
 
18 - 29.10.19 - 18:11
(17) Очевидно же: "вы ввели некорректные данные, попробуйте снова"
   fisher
 
19 - 29.10.19 - 18:12
(11) Это не самое маленькое будет
(17) В нашей вселенной такие числа не нужны
   pechkin
 
20 - 29.10.19 - 18:12
(16) нужно вначале просеять чилса
   pechkin
 
21 - 29.10.19 - 18:13
ну или с конца идти, тогда попроще будет находить
   RomanYS
 
22 - 29.10.19 - 18:13
(15) а 1260 не подойдёт?
   RomanYS
 
23 - 29.10.19 - 18:14
(22) на 8 не делится)
   RomanYS
 
24 - 29.10.19 - 18:17
(0) до 40 слишком банально: раскладываем по степеням простых чисел и берем максимальные степени
   Креатив
 
25 - 29.10.19 - 18:17
(19)Какие Ваши доказательства?(с)
   fisher
 
26 - 29.10.19 - 18:18
Ограничение в N<40, как я понял, спецом подобрано чтобы результат в 64 бита влез. Т.е. в стандартные целочисленные типы данных.
   RomanYS
 
27 - 29.10.19 - 18:18
(25) для 4 проверь
   bolobol
 
28 - 29.10.19 - 18:18
(15) 2520 и на калькуляторе посчитать интуитивно можно, ты разложением проверял?
   Garykom
 
29 - 29.10.19 - 18:19
Рекурсией легко.
Произведение чисел от 1 до N-1, при удалении всех делителей других чисел.

Например для N=10
1*2*3*4 и тут надо удалить 2 или можно поделить на 2
1*3*4*5*6 и тут надо удалить 3, так то еще и 2 но 2 мы уже удалили
1*4*5*6*7*8 удаляем 4
1*5*6*7*8*9 = ?
   fisher
 
30 - 29.10.19 - 18:20
(28) Такой пример прям в условии задачи был.
 
 Рекламное место пустует
   bolobol
 
31 - 29.10.19 - 18:23
(29) У 6 и 9 общие делители - явно неверно
   Креатив
 
32 - 29.10.19 - 18:24
(27)12 получилось.
Возможно ты и прав. Но тут либо контрпимер нужен, либо математическое обоснование.
   bolobol
 
33 - 29.10.19 - 18:24
(32) Математическое обоснование в (13) указано
   RomanYS
 
34 - 29.10.19 - 18:27
П(p[i]^Цел(log(N,p[i]))
П - произведение
p - массив простых чисел до N
log(a, b) - логарифм a по b
   Креатив
 
35 - 29.10.19 - 18:28
(33)А кто сказал, что у меня не НОК в результате получится?
   RomanYS
 
36 - 29.10.19 - 18:34
(35) ты же на 4 проверил? это и есть контрпример
   Креатив
 
37 - 29.10.19 - 18:37
(36)на 4 у меня получилось. На 5 - нет.
   Сияющий в темноте
 
38 - 29.10.19 - 18:41
там сначала массив всех чисел от двкх до Н присеспиь нужно,чтобы выкинуть те числа,которые в нем встречаются в других.
потом можно и перемножить.
   RomanYS
 
39 - 29.10.19 - 18:41
(37) Да у тебя странное решение. Взять N, а потом цикл от 2 до N-1. Простой (убывающий) цикл от N до 2 дал бы правильный ответ
   Garykom
 
40 - 29.10.19 - 18:48
(31) Да ты прав, надо еще на 2 и на 3 поделить ибо 6 и 8 а так же 6 и 9
   Garykom
 
41 - 29.10.19 - 18:51
(40)+ Тогда это просто произведение всех простых чисел от 1 до N-1
   RomanYS
 
42 - 29.10.19 - 19:05
(41) нет,  оно не делится на степени простых чисел больше единицы.
   fisher
 
43 - 29.10.19 - 19:07
(34) Ты крут! До такого математического решения я не додумался. Правда, и решать нужно было на простой арифметике, без логарифмов. Мое решение - просто элегантный отсев повторяемых простых множителей.
   Garykom
 
44 - 29.10.19 - 19:14
(42) Ага тогда (34) самое простое
   fisher
 
45 - 29.10.19 - 19:14
(43) + Вернее, не то чтобы отсев... Просто получилось в одном простом алгоритме красиво совместить и разложение на множители и учет "новых" множителей за один проход и минимальное использование памяти.
   RomanYS
 
46 - 29.10.19 - 19:35
(44) теоретически "простое" и обоснованное - да (34)

(44) (45) На практике самое банальное это (11) только с обратным циклом от N до 2. Проще не придумаешь.
   DTX 4th
 
47 - 29.10.19 - 20:09
(45) Код будет?
   RomanYS
 
48 - 29.10.19 - 20:18
(46) а не, обратный цикл похоже не работает
   Креатив
 
49 - 29.10.19 - 22:19
Можно так.
рез = 1;
Для ш = 2 По N Цикл
   Если рез % ш = 0 Тогда
      Продложить;
   КонецЕсли;
   т = 1;
   Пока т <= N Цикл
      т = т * ш;
   КонецЦикла;
   т = т / ш;
   рез = рез * т;
КонецЦикла
   RomanYS
 
50 - 29.10.19 - 23:27
(49) похоже на правильное
   Конструктор1С
 
51 - 30.10.19 - 06:31
Академические задачки, бессмысленные и беспощадные...
   Сияющий в темноте
 
52 - 30.10.19 - 08:56
если массив заполнить числами от 2 до N и двигаясь по нему умножать результат на встреченное число,а все старшие,которые на него делятся,делить.
   fisher
 
53 - 30.10.19 - 10:10
(47) Не. После (34) это детский лепет. Теперь я стесняюся :)
Но правда же, прикольная задачка?
   fisher
 
54 - 30.10.19 - 10:14
(51) Нифига не бессмысленные. Есть много вариантов решения и чем сильнее ты прошаренный, тем эффективнее сможешь решить.
Это тебе не "Если СуперБизнесУсловиеВыполняется Тогда СуперБизнесФичаПрименяется"
   bolobol
 
55 - 30.10.19 - 10:15
(53) В задаче реализации математической формулы - нет ничего прикольного.

Прикольная задача, например, написать автоматический выходитель из лабиринта, сделать в экселе конструктор лабиринта, сделать выходитель из динамически создаваемого лабиринта в экселе (в экселе визуальная часть подготовлена)
   fisher
 
56 - 30.10.19 - 10:16
(55) В реализации - нет. В выведении - есть. Я поэтому и писал программирование/математика, а не чисто программирование.
   fisher
 
57 - 30.10.19 - 10:18
Ну и еще моих скиллов не хватило сразу понять, что задачу можно свести к простой формуле.
   fisher
 
58 - 30.10.19 - 10:19
Так что может и не зря я в программисты не пошел :)
   bolobol
 
59 - 30.10.19 - 10:19
Интересные задачи на применение игровых методов и Монте-Карло
   fisher
 
60 - 30.10.19 - 10:23
(59) Чем больше исследовательская составляющая - тем интереснее. Ясен пень.
   Креатив
 
61 - 30.10.19 - 10:26
(50)Это та же идея, что у тебя в (34) только без логарифмов и просеивание простых чисел "на лету".
Математически это произведение степеней простых чисел, не превышающих N.
   fisher
 
62 - 30.10.19 - 10:27
(61) Так и есть. В (49) реализация (34). Работоспособность не проверял, но на первый взгляд оно и есть.
   fisher
 
63 - 30.10.19 - 11:00
(34) Слушай, а дай свой ход умозаключений, как ты до этого быстро додумался? Я, что называется, "глазами" понимаю как это работает исходя из существующей закономерности, но видно туплю и простой логической цепочки в голове не складывается. А ты ведь как-то сразу сообразил.
   bolobol
 
64 - 30.10.19 - 11:05
(63) Погуглить самостоятельно решения НОД / НОК никак?
   fisher
 
65 - 30.10.19 - 11:19
(64) Про НОД и НОК я в курсе в целом. Видимо у меня проблема сложить два и два. Подадите убогому?
   RomanYS
 
66 - 30.10.19 - 12:05
(63) смотри (24). В (34) просто формализация.
 
 Рекламное место пустует
   fisher
 
67 - 30.10.19 - 12:31
(66) Да это понятно :) Непонятно формальное доказательство того, что (24) - решение. Видимо я жестко туплю.
   RomanYS
 
68 - 30.10.19 - 13:03
(67) Даже не знаю, где у тебя сомнения.
Непростые множители не рассматриваем вроде очевидно.
Максимальные степени делятся на меньшие - достаточность очевидна.
Меньшие степени не делятся на максимальные - необходимость.
   fisher
 
69 - 30.10.19 - 14:12
(68) Сомнений нет. Я все это понимаю, глядя на закономерность разложения ряда чисел на простые множители. Но как ты это сразу сообразил - для меня непостижимо :) Решил - а вдруг ты сможешь научить меня правильно думать? :)
   Креатив
 
70 - 30.10.19 - 16:08
(69)Это математика. Задачу можно доказать либо с помощью математической индукции, либо как следствие основной теоремы арифметики (об однозначном разложении натурального числа на простые множители).
Вывод учи матчасть(математику).
   fisher
 
71 - 30.10.19 - 17:31
(70) Ну, с индукцией ясно. А докажи-ка, как знающий матчасть, как следствие основной теоремы арифметики.
   fisher
 
72 - 30.10.19 - 17:38
Что доказать можно, и что вообще задача крутится вокруг основной теоремы арифметики - это ежу понятно. Но как раз на самом доказательстве у меня и ступор малехо. А через индукцию не так интересно.
   Креатив
 
73 - 31.10.19 - 09:18
(72)ОТА утверждает, что разложение натурального числа на простые множители единственно с точностью до порядка следования степеней. То есть наше произведение можно представить в виде:
p1^i1*...*pk^ik. Где p1=2, а pk не превосходит квадратного корня из N(что в условии задачи).
И любой сомножитель будет иметь такой же вид, только степени будут не больше, чем в произведении.
Так как степени простых чисел у нас будут "по умолчанию"(мы составляем сомножители из них), то остаётся рассмотреть составные числа. В разложении таких чисел также участвовуют степени простых чисел, которые мы уже рассматривали ранее. Остаётся только показать, что степени простых чисел, которые мы уже "отправили" в результат не меньше, чем в текущем числе. Это очевидным образом следует из того, что если степень в проверяемом числе будет больше, то простое число в этой степени будет больше N, что не может быть, так как мы брали максимальную степень, не превышающую N. (И если её умножить на большее простое число, то произведение будет явно больше N.)
   RomanYS
 
74 - 31.10.19 - 13:33
(73) "а pk не превосходит квадратного корня из N"
На ход рассуждений конечно не влияет, но pk <= N.
   Креатив
 
75 - 31.10.19 - 23:06
(74)Спутал с разложением на множители.
   Креатив
 
76 - 31.10.19 - 23:34
(75)Точнее с условием простоты числа.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.