2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение21.05.2017, 17:13 


29/01/09
428
atlakatl в сообщении #1217829 писал(а):
Дан интервал. В Вашей статье проводится оценка максимальной длины прогрессии, возможных знаменателей.
Только вот нюанс в том ,что это интервал по мере роста оценки $m^*$ сокращается, верхняя граница тоже сокращается не хуже корня (неизвестной степени) - вот вопрос в том как оценить сокращение.. Да и нижняя растет , что сокращает перебор.
Цитата:

А дальше начинаем считать.
В псевдокоде у Вас одни процедуры. Где программа-то?
Цитата:
Дык первая процедура и есть программа - на входе$M_{min},M_{max}$ - на выходе $L_{max} - максимальная  длина$. Логарифмы -корни имеют сложность пропорциональную длине(условно говоря найти делением максимальную степень, либо перебором по разрядам корень)

Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot  10^9]$.
Как происходит проверка конкретного знаменателя? - Я к чему? Вы утверждаете, что алгоритм у Вас "экспоненциальный".
Потому что верхняя граница , как мне кажется ( о чем и стоит вопрос) и останется функцией намного большего роста, чем логарифм верхней границы ака длины верхней границы...
Цитата:


Т.е. кроме сканирования по всему (или его конечной части) интервалу для определения первого члена не видно.
А значит, время счёта тупо пропорциональна длине интервала. И никакой экспоненты.


Ну думать или спрашивать об оптимизации никому не запрещено...Тем более есть такая вещь в музыке - называется октава...Там ведь для практических целей создания музыкальных инструментов аппроксимируют $2^{\frac{i}{12}}$ ближайшими цепными дробями....вот и думаю нельзя ли как -то и здесь применить цепные дроби для сокращения поиска - их числители знаменатели ведь тоже растут экспоненциально с каждым шагом аппроксимации

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение21.05.2017, 17:26 
Заслуженный участник


20/08/14
11061
Россия, Москва
Dmitriy40 в сообщении #1217831 писал(а):
Если надо найти не минимальное $N$, а в заданном интервале, то можно найти минимальное, а потом домножить на минимальный коэффициент для попадания в заданный интервал.
...
И тогда перебор вообще не нужен, можно обойтись прямыми вычислениями, с временем $O(1)$.
Вот с этим я промахнулся, не для всяких интервалов это находит ответ. Например для интервала $[8000, \, 16000]$ ни одной из двух последовательностей длиной $n=5$ таким способом не находится. :-( Значит без перебора всё же никуда.
Но можно ограничиться перебором лишь по $p$, начиная от указанного выше минимального вверх, находя коэфициент $c$ для попадания выражения $cp^{n-1}$ в заданный интервал и проверяя последнее число на попадание в интервал. Т.е. перебор будет весьма и весьма ограниченным, буквально несколько разных значений, в остальном же прямые вычисления.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение21.05.2017, 23:14 


29/01/09
428
atlakatl в сообщении #1217829 писал(а):
Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot  10^9]$.


кстати тоже детский интервал - его можно тоже не на егэ конечно (но не какой нибудь средненькой олимпиаде для 9 класса давать). Потому как уже на втором шаге итераций по s (s=3) можно найти последовательность длины равную 5. А значит перебор падает до верхней границы s=100 (потому что убывающие последовательности длины 6 должны начинаться с некоторого кратного пятой степени какого-то натурального числа) ...Тут похоже какая-то нетривиальная сложность перебора с зависимостью как от $M_{min}$, так и от $\frac{M_{max}}{M_{min}}$ (ну либо числа детские - нужны монструозные числа... либо недостаточная сложность границ, либо их отношений)

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 00:13 
Заслуженный участник


20/08/14
11061
Россия, Москва
atlakatl в сообщении #1217829 писал(а):
Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot  10^9]$.
Если я прав в своей гипотезе, то в данном интервале должны быть последовательности из 12-ти членов (например 1088391168, 1269789696, 1481421312, 1728324864, 2016379008, 2352442176, 2744515872, 3201935184, 3735591048, 4358189556, 5084554482, 5931980229 - возможно и единственная) и не должно быть ни одной из 13-ти членов. Причём это легко посчитано руками на калькуляторе, даже без программ.

(PS. Числа.)

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

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 01:29 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва

(Dmitriy40)

Dmitriy40 в сообщении #1217905 писал(а):
Прошу прощения что числа не в виде формул, но тогда они выглядят по уродски, даже с разбивкой на отдельные формулы.
Что Вы имеете в виду? Шрифт не нравится?
$1\,088\,391\,168$, $1\,269\,789\,696$, $1\,481\,421\,312$, $1\,728\,324\,864$, $2\,016\,379\,008$, $2\,352\,442\,176$, $2\,744\,515\,872$, $3\,201\,935\,184$, $3\,735\,591\,048$, $4\,358\,189\,556$, $5\,084\,554\,482$, $5\,931\,980\,229$.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 01:39 


29/01/09
428
Dmitriy40 в сообщении #1217905 писал(а):
atlakatl в сообщении #1217829 писал(а):
Давайте возьмём "взрослый" интервал $[10^9, 6 \cdot  10^9]$.
Если я прав в своей гипотезе, то в данном интервале должны быть последовательности из 12-ти членов (например 1088391168, 1269789696, 1481421312, 1728324864, 2016379008, 2352442176, 2744515872, 3201935184, 3735591048, 4358189556, 5084554482, 5931980229 - возможно и единственная) и не должно быть ни одной из 13-ти членов. Причём это легко посчитано руками на калькуляторе, даже без программ.

(PS. Числа.)

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


Я тоже посчитал в Mathematica за 70 шагов (с таким интервалом действительно можно в олимпиаду выкладывать)... Ща выложу листинг.. Да пока проверял в псевдокоде три бага нашел...то же исправлю и выложу....


Итак листинг Mathematica cо итерациями для этого случая http://my-files.ru/q2s8hi (в pdf)

Сам исходный файл Mathematica http://my-files.ru/t8z8pg (с расширением .nb)

Текст решения с исправленным псеводокодом в решении http://my-files.ru/nvkatv (в pdf)

ЗЫ

Извиняюсь сразу за оффтопик, и не камень в чужой огород...А почему так латек коряво выглядит. Это из-за моих настроек, или движок ренедерит в картинку - а потом ее вставляет в текст? На других сайтах как-то покрасивше выглядит - особенно если работает MathJaX

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 02:15 
Заслуженный участник


20/08/14
11061
Россия, Москва

(Числа)

Someone в сообщении #1217920 писал(а):
Что Вы имеете в виду?
Не, это похоже я ошибся при редактировании формулы, знаки $ расставил, а вот теги math оставил лишь вокруг всей последовательности, ну все числа и слились в одну формулу криво. Сейчас ещё раз перепроверил, теперь отображается правильно, если каждое число и $ и math обрамлено. Раздражает эта вот особенность движка, с тегами math, как будто просто $ мало.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 06:26 


23/01/07
3415
Новосибирск
pppppppo_98 в сообщении #1217419 писал(а):
Пусть имеется отрезок ряда натуральных чисел - найти длину наибольшей геометрической прогрессии, лежащую в этом отрезке(скажем $[M_{min},M_{max}]$)

Как мне видится, на заданном интервале необходимо определить максимальные одинаковые степени двух наибольших последовательных натуральных чисел. Например, в ЕГЭ-шной задаче: $6^3=216, 7^3=343$.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 06:34 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Батороев в сообщении #1217926 писал(а):
Как мне видится, на заданном интервале необходимо определить максимальные одинаковые степени двух наибольших последовательных натуральных чисел. Например, в ЕГЭ-шной задаче: $6^3=216, 7^3=343$.
Это не так. Возьмите ЕГЭшную задачу и замените в ней обе границы промежутка на в два раза большие.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 07:12 


23/01/07
3415
Новосибирск
Mikhail_K в сообщении #1217928 писал(а):
Возьмите ЕГЭшную задачу и замените в ней обе границы промежутка на в два раза большие.

Получил четыре числа: $343;392;448;512$. У Вас больше?

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 07:16 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Батороев в сообщении #1217930 писал(а):
Получил четыре числа: $343;392;448;512$. У Вас больше?
Вы увеличили вдвое обе границы промежутка? и какая нижняя граница?

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 07:22 


23/01/07
3415
Новосибирск

(Оффтоп)

Тьфу на меня! Отвлекся на основную работу и напортачил...


-- 22 май 2017 11:43 --

Получил варианты только по три числа.

-- 22 май 2017 12:11 --

(Оффтоп)

Батороев в сообщении #1217926 писал(а):
Как мне видится

Значит, не все виделось. :shock: т.к. существует цепочка из четырех удвоенных ЕГЭ-шных.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 09:24 


29/01/09
428
Кто подскажет. А какие существуют библиотеки с/с++ для работы с действительно целыми длинными числами (ну скажем в десяток-сотню тысяч цифр). Ну и соответственно не сильно смещенный генератор случайных последовательностей такой длины.

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 09:31 
Заслуженный участник
Аватара пользователя


06/10/08
6422
pppppppo_98 в сообщении #1217944 писал(а):
Кто подскажет. А какие существуют библиотеки с/с++ для работы с действительно целыми длинными числами (ну скажем в десяток-сотню тысяч цифр). Ну и соответственно не сильно смещенный генератор случайных последовательностей такой длины.
https://gmplib.org/

 Профиль  
                  
 
 Re: ЕГЭшная задача с совсем не школьным продолжением
Сообщение22.05.2017, 11:02 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Попроще в обращении NTL. Я её когда-то в C++Builder компилировал. Насколько я помню, её можно откомпилировать так, чтобы она использовала GMP в качестве вычислительного ядра. Но для компиляции GMP мне пришлось возиться с MinGW и MSYS.

(Dmitriy40)

Dmitriy40 в сообщении #1217923 писал(а):
Не, это похоже я ошибся при редактировании формулы, знаки $ расставил, а вот теги math оставил лишь вокруг всей последовательности
Ну да, там появляется абзацный отступ и перенос на следующую строку, и, поскольку результат выдаётся в виде картинки, выглядит действительно безобразно. И ещё надо удалить лишние знаки доллара, которые появляются после нажатия на кнопку math (раньше их не было; я не заметил, когда они появились — похоже, из-за начинающих пользователей, которые вечно math ставят, а знаки доллара забывают).

Dmitriy40 в сообщении #1217923 писал(а):
Раздражает эта вот особенность движка, с тегами math, как будто просто $ мало.
Тут Вы, похоже, что-то не знаете. Знаков доллара вполне достаточно, а теги расставляются автоматически, хотя и неудобным образом: если случайно знак доллара пропустишь, то теги расставятся так, что придётся их вычищать вручную. Кроме того, если текст формулы разбит на несколько строк, то парсер её не распознаёт, и тег math нужно вставлять вручную.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K, YandexBot [bot]


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group