Парни, помогите решить задачу не просто программированием а математическим решением.. / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Парни, помогите решить задачу не просто программированием а математическим решением..

29 сообщений из 29, показаны все 2 страниц

все

Парни, помогите решить задачу не просто программированием а математическим решением..

#39012703

Valerii

Участник

Сообщения: 754

Рейтинг: 0 / 0

Задача:
Имеется алгоритм:

Имеется Значение N
x = 1
y = 2
Выполнять пока x<>0 AND y * y <= N
x = N MOD y
y = y + 1
конец

печать значения: y - 1

Назовите минимальное и максимальное значение N от 1 до 300 при котором результат алгоритма выдавала значение 11

Любые идеи are welcome!!!!

...

Рейтинг:

0 / 0

21.07.2015, 19:45

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39012744

Mozok

Участник

Откуда: Киев

Сообщения: 969

Рейтинг: 0 / 0

Valerii,

вроде как 127 и 139

...

Рейтинг:

0 / 0

21.07.2015, 21:21

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39012748

Mozok

Участник

Откуда: Киев

Сообщения: 969

Рейтинг: 0 / 0

Valerii,

хотя нет, 121 тоже подходит. Тогда 121 и 253.

...

Рейтинг:

0 / 0

21.07.2015, 21:25

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39012896

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

Доказательство не полное, из него не следует явно почему простые числа которые были приведены выше могут быть решением(пусть не оптимальным), попробуйте сами дополнить ;)

...

Рейтинг:

0 / 0

22.07.2015, 02:45

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39012899

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

Т.е. множеством решений будут числа 11k где к простые числа больше либо равные 11, и кроме того будут ещё некоторые числа(в данном случае они не влияют на минимум и максимум целевой функции), их попробуйте получить самостоятельно

...

Рейтинг:

0 / 0

22.07.2015, 02:49

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39013972

Valerii

Участник

Сообщения: 754

Рейтинг: 0 / 0

SashaMercury,

Спасибо!!! ТО что надо ...

...

Рейтинг:

0 / 0

22.07.2015, 21:44

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39014073

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

ValeriiSashaMercury,

Спасибо!!! ТО что надо ...

Но не до конца. Из доказательства не следует что в множестве решений(при другой верхней границе) могут быть числа 127 и 139. Попробуйте закончить самостоятельно

...

Рейтинг:

0 / 0

23.07.2015, 01:37

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39016227

Valerii

Участник

Сообщения: 754

Рейтинг: 0 / 0

SashaMercuryValeriiSashaMercury,

Спасибо!!! ТО что надо ...

Но не до конца. Из доказательства не следует что в множестве решений(при другой верхней границе) могут быть числа 127 и 139. Попробуйте закончить самостоятельно

Нет, этого достаточно - нужны 2 значения макс и мин для выполнения условия
121 и 253 - как раз то что надо по Вашей логике...

...

Рейтинг:

0 / 0

26.07.2015, 21:33

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39016328

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

ValeriiSashaMercuryпропущено...

Но не до конца. Из доказательства не следует что в множестве решений(при другой верхней границе) могут быть числа 127 и 139. Попробуйте закончить самостоятельно

Нет, этого достаточно - нужны 2 значения макс и мин для выполнения условия
121 и 253 - как раз то что надо по Вашей логике...

Но если бы верхняя граница была не 300, а например 139, то мои рассуждения выше были бы неверны

...

Рейтинг:

0 / 0

27.07.2015, 09:12

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39021695

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

ValeriiЗадача:
Имеется алгоритм:

Имеется Значение N
x = 1
y = 2
Выполнять пока x<>0 AND y * y <= N
x = N MOD y
y = y + 1
конец

печать значения: y - 1

Назовите минимальное и максимальное значение N от 1 до 300 при котором результат алгоритма выдавала значение 11

Любые идеи are welcome!!!!Да это же почти решето Эратосфена для проверки простоты числа N. Точнее, поиск наименьшего простого делителя. Ну а поскольку НПД N должно быть число 11, то само N должно быть вида... стоп, этак я за вас всю работу сделаю :)
Лучше просто дам наводку: https://ru.wikipedia.org/wiki/Основная_теорема_арифметики

...

Рейтинг:

0 / 0

03.08.2015, 13:41

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023641

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

ValeriiИмеется Значение N
x = 1
y = 2
Выполнять пока x<>0 AND y * y <= N
x = N MOD y
y = y + 1
конец

печать значения: y - 1

Назовите минимальное и максимальное значение N от 1 до 300 при котором результат алгоритма выдавала значение 11

Тут X надо выкинуть, он только путает, т.е. это тоже самое

Код: sql

1.
2.
3.
4.
5.
6.

y = 2
Выполнять пока y * y <= N
    Если N MOD y = 0 Тогда N = 0 // для выхода из цикла
    y = y + 1
конец
Печать y - 1

т.е. задача сводится к тому что N должно делиться без остатка на 11 и не делиться на меньшие простые, т.е. 2,3,5,7

...

Рейтинг:

0 / 0

05.08.2015, 15:53

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023651

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

Dima Tт.е. задача сводится к тому что N должно делиться без остатка на 11 и не делиться на меньшие простые, т.е. 2,3,5,7

нет, контрпример был выше

Mozok 127 и 139

...

Рейтинг:

0 / 0

05.08.2015, 15:57

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023675

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SashaMercuryDima Tт.е. задача сводится к тому что N должно делиться без остатка на 11 и не делиться на меньшие простые, т.е. 2,3,5,7

нет, контрпример был выше

Mozok 127 и 139
это ошибка, 121 меньше, автор поправился 17918912

У меня все верно.

Дальше поиск мин/макс. с учетом y * y <= N
т.е. минимальное N = 11*11 = 121
максимальное чуть сложнее 11 * 11 * 11 = 1331, т.е. >300 значит ответ 11*К где К простое > 11
300 / 11 = 27,27 т.е. K < 27 отсюда K = 23
максимум N = 11 * 23 = 253

...

Рейтинг:

0 / 0

05.08.2015, 16:12

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023687

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

Dima TSashaMercuryпропущено...

нет, контрпример был выше

пропущено...

это ошибка, 121 меньше, автор поправился 17918912

У меня все верно.

Дальше поиск мин/макс. с учетом y * y <= N
т.е. минимальное N = 11*11 = 121
максимальное чуть сложнее 11 * 11 * 11 = 1331, т.е. >300 значит ответ 11*К где К простое > 11
300 / 11 = 27,27 т.е. K < 27 отсюда K = 23
максимум N = 11 * 23 = 253

нет, это не ошибка. Возьмите верхнюю границу другой.

...

Рейтинг:

0 / 0

05.08.2015, 16:19

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023694

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SashaMercuryнет, это не ошибка. Возьмите верхнюю границу другой.
121 < 127 всегда, поэтому 127 минимумом быть не может :)

Двиганье верхней границы изменит только максимум, но это уже за рамками задачи. По задаче 300

...

Рейтинг:

0 / 0

05.08.2015, 16:26

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023937

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

Dima TSashaMercuryнет, это не ошибка. Возьмите верхнюю границу другой.
121 < 127 всегда, поэтому 127 минимумом быть не может :)

Двиганье верхней границы изменит только максимум, но это уже за рамками задачи. По задаче 300

Если бы верхняя граница в условиях задачи была 128, то какой вы дали бы ответ согласно вашей логике ?

...

Рейтинг:

0 / 0

06.08.2015, 01:40

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023969

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SashaMercuryЕсли бы верхняя граница в условиях задачи была 128, то какой вы дали бы ответ согласно вашей логике ?
121 минимум и 127 максимум.

Это частный случай, т.к. при условии 121 <= N < 11*12 любое простое даст 11.
т.е. максимумом будет максимальное простое <= N

...

Рейтинг:

0 / 0

06.08.2015, 07:12

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023977

SashaMercury

Участник

Откуда: Москва

Сообщения: 2 595

Рейтинг: 0 / 0

Dima TSashaMercuryЕсли бы верхняя граница в условиях задачи была 128, то какой вы дали бы ответ согласно вашей логике ?
121 минимум и 127 максимум.

Это частный случай, т.к. при условии 121 <= N < 11*12 любое простое даст 11.
т.е. максимумом будет максимальное простое <= N

Как часто будут возникать так называемые 'частные случаи' ? Откуда согласно вашему алгоритму следует что перед число 300 нет такого числа (частного случая)?

...

Рейтинг:

0 / 0

06.08.2015, 08:00

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023982

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SashaMercuryКак часто будут возникать так называемые 'частные случаи' ? Откуда согласно вашему алгоритму следует что перед число 300 нет такого числа (частного случая)?
Только на диапазоне 121 <= N < 132, т.к. на простом > 121 будет выходить из цикла по условию y * y <= N с ответом 11.
При N > 132 простые будут давать ответ 12 и более.

Второй частный случай: при N < 121 нет решений.

Это все частные случаи для начала от 1. Если нижнюю границу двигать, то еще будут частные случаи.

Не веришь - перебор написать несложно. Я не запускал, выводы теоретические.

...

Рейтинг:

0 / 0

06.08.2015, 08:25

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023983

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Напутал немного, верх 'частного случая' не 132 (11*12), а 144 (12*12)

...

Рейтинг:

0 / 0

06.08.2015, 08:28

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023986

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

SashaMercuryКак часто будут возникать так называемые 'частные случаи' ?Ну так для каждого интервала будет свой ответ

Алгоритм ищет наименьший делитель числа N и должен выдавать 11 - значит, (сообщает копетан) N делится на 11 и не делится на (простые) числа меньше 11.
Т.е. все подходящие N будут иметь вид (осн.т.ариф.)

Код: plaintext

p ₁  ^{k1  * p ₂  ^{k2  * ... p _T  ^kT}}

, где:
-все p _i - простые
-для любого i p _i <p _i+1
-p ₁ =11
-либо k ₁ >=2 и T>=1, либо k ₁ >=1 и T>=1.
Последнее - потому что 11<=sqrt(N), следовательно, N>=121.
Dima Tт.е. максимумом будет максимальное простое <= NЭээ... мы вообще-то ищем это самое максимальное N... и, кстати, простого способа подбора в случае произвольно заданных границ тут не прослеживается.

...

Рейтинг:

0 / 0

06.08.2015, 08:38

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023987

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

tanglir-либо k ₁ >=2 и T>=1, либо k ₁ >=1 и T>=2.всё-таки опечатался

...

Рейтинг:

0 / 0

06.08.2015, 08:39

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023991

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

tanglirDima Tт.е. максимумом будет максимальное простое <= NЭээ... мы вообще-то ищем это самое максимальное N...
Очепятка, <= концу проверяемого диапазона.
tanglir и, кстати, простого способа подбора в случае произвольно заданных границ тут не прослеживается.
Перебор 11 в начале диапазона и 11 в конце. Быстро и просто

...

Рейтинг:

0 / 0

06.08.2015, 08:43

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39023993

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Dima TПеребор 11 в начале диапазона и 11 в конце. Быстро и просто
Не поможет.

Да и пофиг. Исходная задача стояла 1-300.

...

Рейтинг:

0 / 0

06.08.2015, 08:46

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39024123

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

Dima TПеребор 11 в начале диапазона и 11 в конце.чёрт, и правда, все решения должны же делиться на 11

...

Рейтинг:

0 / 0

06.08.2015, 11:07

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39024126

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

Dima TНе поможет.ну, можно и побольше перебрать

...

Рейтинг:

0 / 0

06.08.2015, 11:08

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39024127

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

В конце концов, любую задачу можно решить перебором, вопрос только во времени, а такого ограничения в условии нет.

...

Рейтинг:

0 / 0

06.08.2015, 11:09

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39024153

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

быстрее всего перебирать по таблице простых от 11. т.е. искать максимум

Код: sql

N = 11*p1*p2*...*pN <= предел поиска

где все p простые >=11

...

Рейтинг:

0 / 0

06.08.2015, 11:25

| Ответить | Цитировать | Написать

Парни, помогите решить задачу не просто программированием а математическим решением..

#39024339

tanglir

Участник

Сообщения: 30 379

Рейтинг: 0 / 0

ну да, о чём я и писал, для относительно больших чисел - только перебором

...

Рейтинг:

0 / 0

06.08.2015, 13:48

| Ответить | Цитировать | Написать

29 сообщений из 29, показаны все 2 страниц

все

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?all=1&fid=16&tid=1340958]:	0ms
get settings:	11ms
get forum list:	20ms
check forum access:	4ms
check topic access:	4ms
track hit:	180ms
get topic data:	8ms
get forum data:	2ms
get page messages:	64ms
get tp. blocked users:	1ms
others:	229ms

total:	523ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы