|
Задачка по программированию/математике 🠗 (Волшебник 30.10.2019 09:36) | ☑ | ||
---|---|---|---|---|
0
fisher
29.10.19
✎
17:41
|
Понравилась задачка по программированию/математике. Из тех, что первокурсникам-программистам дают. Нашел элегантное решение и радуюсь. Может, надо было в программисты идти? :))
"Напишите функцию, которая найдет самое маленькое число, которое делится нацело на все числа от 1 до N (N<40, вводится пользователем)" |
|||
1
mikecool
29.10.19
✎
17:43
|
я таких мозгодробилок(для меня иначе и не назовешь) на питоне штук 40 нарешал )
|
|||
2
fisher
29.10.19
✎
17:44
|
(1) Млдц!
|
|||
3
Мимохожий Однако
29.10.19
✎
17:44
|
(0) Я за тебя тоже радуюсь.
|
|||
4
fisher
29.10.19
✎
17:47
|
(3) Дык! За такого красавчика грех не порадоваться! Затем и поделился!
|
|||
5
aleks_default
29.10.19
✎
17:48
|
А мне грустно, потому что вспоминил школу и уроки информатики в 5-ом классе...
|
|||
6
hhhh
29.10.19
✎
17:49
|
(4) ну, выкладывай, потестируем
|
|||
7
dmt
29.10.19
✎
17:50
|
(0)
> Может, надо было в программисты идти? поздно (( |
|||
8
fisher
29.10.19
✎
17:50
|
(6) Шиш тебе! Сам любоваться буду!
Хочешь и себе такую лапочку - сам пиши! (7) Отож :( |
|||
9
hhhh
29.10.19
✎
17:54
|
(8) ок. не хочу я эту лапочку. Просто можно было проверить. Наверняка какую-то бредятину ведь написал, и радуешься.
|
|||
10
fisher
29.10.19
✎
17:56
|
Чем меня всегда раздражали программные реализации математических концепций - так это если нет соответствующей математической базы, то хрена лысого ты разберешься, как эта программа работает. Ну т.е. типа угадал все буквы - а слова назвать не можешь.
Тут прелесть в том, что математическая база, как было правильно замечено, укладывается в школьную программу. И формулировка задачи очень простая. |
|||
11
Креатив
29.10.19
✎
17:56
|
(0)Так вроде всё просто.
r := n; для ш := 2 до n-1 цикл Если r mod ш <> 0 То r := r * ш; КонецЕсли; КонецЦикла; За смесь языком простите. |
|||
12
hhhh
29.10.19
✎
17:59
|
(10) самое простейшее решение, нашел за одну минуту
Массив = Новый Массив; Массив.Добавить(1); Массив.Добавить(2); Массив.Добавить(6); Массив.Добавить(12); Массив.Добавить(60); ... Возврат Массив[N-1]; |
|||
13
pechkin
29.10.19
✎
18:00
|
это же НОК.
НОК = П / НОД |
|||
14
pechkin
29.10.19
✎
18:02
|
НОД находится алгоритмом Эвклида
|
|||
15
fisher
29.10.19
✎
18:02
|
Для проверки: для N = 10 ответ 2520
|
|||
16
fisher
29.10.19
✎
18:03
|
(13) Молодец! Только если в лоб через НОД решать для нескольких чисел, решение будет не шибко элегантным.
|
|||
17
hhhh
29.10.19
✎
18:08
|
(15) а если N = 40 000 000, сколько получается?
|
|||
18
bolobol
29.10.19
✎
18:11
|
(17) Очевидно же: "вы ввели некорректные данные, попробуйте снова"
|
|||
19
fisher
29.10.19
✎
18:12
|
(11) Это не самое маленькое будет
(17) В нашей вселенной такие числа не нужны |
|||
20
pechkin
29.10.19
✎
18:12
|
(16) нужно вначале просеять чилса
|
|||
21
pechkin
29.10.19
✎
18:13
|
ну или с конца идти, тогда попроще будет находить
|
|||
22
RomanYS
29.10.19
✎
18:13
|
(15) а 1260 не подойдёт?
|
|||
23
RomanYS
29.10.19
✎
18:14
|
(22) на 8 не делится)
|
|||
24
RomanYS
29.10.19
✎
18:17
|
(0) до 40 слишком банально: раскладываем по степеням простых чисел и берем максимальные степени
|
|||
25
Креатив
29.10.19
✎
18:17
|
(19)Какие Ваши доказательства?(с)
|
|||
26
fisher
29.10.19
✎
18:18
|
Ограничение в N<40, как я понял, спецом подобрано чтобы результат в 64 бита влез. Т.е. в стандартные целочисленные типы данных.
|
|||
27
RomanYS
29.10.19
✎
18:18
|
(25) для 4 проверь
|
|||
28
bolobol
29.10.19
✎
18:18
|
(15) 2520 и на калькуляторе посчитать интуитивно можно, ты разложением проверял?
|
|||
29
Garykom
гуру
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 = ? |
|||
30
fisher
29.10.19
✎
18:20
|
(28) Такой пример прям в условии задачи был.
|
|||
31
bolobol
29.10.19
✎
18:23
|
(29) У 6 и 9 общие делители - явно неверно
|
|||
32
Креатив
29.10.19
✎
18:24
|
(27)12 получилось.
Возможно ты и прав. Но тут либо контрпимер нужен, либо математическое обоснование. |
|||
33
bolobol
29.10.19
✎
18:24
|
(32) Математическое обоснование в (13) указано
|
|||
34
RomanYS
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)А кто сказал, что у меня не НОК в результате получится?
|
|||
36
RomanYS
29.10.19
✎
18:34
|
(35) ты же на 4 проверил? это и есть контрпример
|
|||
37
Креатив
29.10.19
✎
18:37
|
(36)на 4 у меня получилось. На 5 - нет.
|
|||
38
Сияющий в темноте
29.10.19
✎
18:41
|
там сначала массив всех чисел от двкх до Н присеспиь нужно,чтобы выкинуть те числа,которые в нем встречаются в других.
потом можно и перемножить. |
|||
39
RomanYS
29.10.19
✎
18:41
|
(37) Да у тебя странное решение. Взять N, а потом цикл от 2 до N-1. Простой (убывающий) цикл от N до 2 дал бы правильный ответ
|
|||
40
Garykom
гуру
29.10.19
✎
18:48
|
(31) Да ты прав, надо еще на 2 и на 3 поделить ибо 6 и 8 а так же 6 и 9
|
|||
41
Garykom
гуру
29.10.19
✎
18:51
|
(40)+ Тогда это просто произведение всех простых чисел от 1 до N-1
|
|||
42
RomanYS
29.10.19
✎
19:05
|
(41) нет, оно не делится на степени простых чисел больше единицы.
|
|||
43
fisher
29.10.19
✎
19:07
|
(34) Ты крут! До такого математического решения я не додумался. Правда, и решать нужно было на простой арифметике, без логарифмов. Мое решение - просто элегантный отсев повторяемых простых множителей.
|
|||
44
Garykom
гуру
29.10.19
✎
19:14
|
(42) Ага тогда (34) самое простое
|
|||
45
fisher
29.10.19
✎
19:14
|
(43) + Вернее, не то чтобы отсев... Просто получилось в одном простом алгоритме красиво совместить и разложение на множители и учет "новых" множителей за один проход и минимальное использование памяти.
|
|||
46
RomanYS
29.10.19
✎
19:35
|
(44) теоретически "простое" и обоснованное - да (34)
(44) (45) На практике самое банальное это (11) только с обратным циклом от N до 2. Проще не придумаешь. |
|||
47
DTX 4th
29.10.19
✎
20:09
|
(45) Код будет?
|
|||
48
RomanYS
29.10.19
✎
20:18
|
(46) а не, обратный цикл похоже не работает
|
|||
49
Креатив
29.10.19
✎
22:19
|
Можно так.
рез = 1; Для ш = 2 По N Цикл Если рез % ш = 0 Тогда Продложить; КонецЕсли; т = 1; Пока т <= N Цикл т = т * ш; КонецЦикла; т = т / ш; рез = рез * т; КонецЦикла |
|||
50
RomanYS
29.10.19
✎
23:27
|
(49) похоже на правильное
|
|||
51
Конструктор1С
30.10.19
✎
06:31
|
Академические задачки, бессмысленные и беспощадные...
|
|||
52
Сияющий в темноте
30.10.19
✎
08:56
|
если массив заполнить числами от 2 до N и двигаясь по нему умножать результат на встреченное число,а все старшие,которые на него делятся,делить.
|
|||
53
fisher
30.10.19
✎
10:10
|
(47) Не. После (34) это детский лепет. Теперь я стесняюся :)
Но правда же, прикольная задачка? |
|||
54
fisher
30.10.19
✎
10:14
|
(51) Нифига не бессмысленные. Есть много вариантов решения и чем сильнее ты прошаренный, тем эффективнее сможешь решить.
Это тебе не "Если СуперБизнесУсловиеВыполняется Тогда СуперБизнесФичаПрименяется" |
|||
55
bolobol
30.10.19
✎
10:15
|
(53) В задаче реализации математической формулы - нет ничего прикольного.
Прикольная задача, например, написать автоматический выходитель из лабиринта, сделать в экселе конструктор лабиринта, сделать выходитель из динамически создаваемого лабиринта в экселе (в экселе визуальная часть подготовлена) |
|||
56
fisher
30.10.19
✎
10:16
|
(55) В реализации - нет. В выведении - есть. Я поэтому и писал программирование/математика, а не чисто программирование.
|
|||
57
fisher
30.10.19
✎
10:18
|
Ну и еще моих скиллов не хватило сразу понять, что задачу можно свести к простой формуле.
|
|||
58
fisher
30.10.19
✎
10:19
|
Так что может и не зря я в программисты не пошел :)
|
|||
59
bolobol
30.10.19
✎
10:19
|
Интересные задачи на применение игровых методов и Монте-Карло
|
|||
60
fisher
30.10.19
✎
10:23
|
(59) Чем больше исследовательская составляющая - тем интереснее. Ясен пень.
|
|||
61
Креатив
30.10.19
✎
10:26
|
(50)Это та же идея, что у тебя в (34) только без логарифмов и просеивание простых чисел "на лету".
Математически это произведение степеней простых чисел, не превышающих N. |
|||
62
fisher
30.10.19
✎
10:27
|
(61) Так и есть. В (49) реализация (34). Работоспособность не проверял, но на первый взгляд оно и есть.
|
|||
63
fisher
30.10.19
✎
11:00
|
(34) Слушай, а дай свой ход умозаключений, как ты до этого быстро додумался? Я, что называется, "глазами" понимаю как это работает исходя из существующей закономерности, но видно туплю и простой логической цепочки в голове не складывается. А ты ведь как-то сразу сообразил.
|
|||
64
bolobol
30.10.19
✎
11:05
|
(63) Погуглить самостоятельно решения НОД / НОК никак?
|
|||
65
fisher
30.10.19
✎
11:19
|
(64) Про НОД и НОК я в курсе в целом. Видимо у меня проблема сложить два и два. Подадите убогому?
|
|||
66
RomanYS
30.10.19
✎
12:05
|
(63) смотри (24). В (34) просто формализация.
|
|||
67
fisher
30.10.19
✎
12:31
|
(66) Да это понятно :) Непонятно формальное доказательство того, что (24) - решение. Видимо я жестко туплю.
|
|||
68
RomanYS
30.10.19
✎
13:03
|
(67) Даже не знаю, где у тебя сомнения.
Непростые множители не рассматриваем вроде очевидно. Максимальные степени делятся на меньшие - достаточность очевидна. Меньшие степени не делятся на максимальные - необходимость. |
|||
69
fisher
30.10.19
✎
14:12
|
(68) Сомнений нет. Я все это понимаю, глядя на закономерность разложения ряда чисел на простые множители. Но как ты это сразу сообразил - для меня непостижимо :) Решил - а вдруг ты сможешь научить меня правильно думать? :)
|
|||
70
Креатив
30.10.19
✎
16:08
|
(69)Это математика. Задачу можно доказать либо с помощью математической индукции, либо как следствие основной теоремы арифметики (об однозначном разложении натурального числа на простые множители).
Вывод учи матчасть(математику). |
|||
71
fisher
30.10.19
✎
17:31
|
(70) Ну, с индукцией ясно. А докажи-ка, как знающий матчасть, как следствие основной теоремы арифметики.
|
|||
72
fisher
30.10.19
✎
17:38
|
Что доказать можно, и что вообще задача крутится вокруг основной теоремы арифметики - это ежу понятно. Но как раз на самом доказательстве у меня и ступор малехо. А через индукцию не так интересно.
|
|||
73
Креатив
31.10.19
✎
09:18
|
(72)ОТА утверждает, что разложение натурального числа на простые множители единственно с точностью до порядка следования степеней. То есть наше произведение можно представить в виде:
p1^i1*...*pk^ik. Где p1=2, а pk не превосходит квадратного корня из N(что в условии задачи). И любой сомножитель будет иметь такой же вид, только степени будут не больше, чем в произведении. Так как степени простых чисел у нас будут "по умолчанию"(мы составляем сомножители из них), то остаётся рассмотреть составные числа. В разложении таких чисел также участвовуют степени простых чисел, которые мы уже рассматривали ранее. Остаётся только показать, что степени простых чисел, которые мы уже "отправили" в результат не меньше, чем в текущем числе. Это очевидным образом следует из того, что если степень в проверяемом числе будет больше, то простое число в этой степени будет больше N, что не может быть, так как мы брали максимальную степень, не превышающую N. (И если её умножить на большее простое число, то произведение будет явно больше N.) |
|||
74
RomanYS
31.10.19
✎
13:33
|
(73) "а pk не превосходит квадратного корня из N"
На ход рассуждений конечно не влияет, но pk <= N. |
|||
75
Креатив
31.10.19
✎
23:06
|
(74)Спутал с разложением на множители.
|
|||
76
Креатив
31.10.19
✎
23:34
|
(75)Точнее с условием простоты числа.
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |