ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
25 сообщений из 208, страница 2 из 9
  2  все
Алгоритмы
    #39162812
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T,

осталось написать функцию сравнения башен )
...
Рейтинг: 0 / 0
04.02.2016, 12:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162822
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Aleksandr Sharahov,
А все допер.
Не учел это -"В первой строке входного файла INPUT.TXT задается число башен N ". Считал 10=0. Невнимательность.
...
Рейтинг: 0 / 0
04.02.2016, 12:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39162830
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Станислав С...кийне так, немного:
точно, это студенческая классика: "введите кол-во наборов", "введите размер набора 1", "введите элемент 1 набора 1" и т.д.
...
Рейтинг: 0 / 0
04.02.2016, 12:20
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163006
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги. Я для удобства перепишу этот тесткейс. Добавлю номера строк в Given для удобства.
 

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
When:

10
1)4 2 2 2 2 2
2)1 2 2
3)1 3 2
4)1 2 3
5)3 2 2 2 2
6)2 2 2 2
7)1 3 3
8)3 3 3 3 3
9)2 4 3 3
10)2 2 3 4

Then:

2 4 3 6 7 5 9 10 1 8



В уже отсортированном виде. Сверху-вниз от меньших к большим.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1 2 2
1 2 3
1 3 2
2 2 (2 2)
1 3 (3)
3 2 2 2 2
2 4 3 3
2 2 3 4
4 2 2 2 2 2
3 3 3 3 3



Несколько мыслей.
1) Возвозить степень в степень - рискованно с точки зрения типов данных. Можно не влезть ни в какой
тип а даже если заюзать символьную арифметику - непродуктивно и долго. Ведь задача стоит не вычислить
а сравнить. Поэтому предлагаю до последнего не заниматься поиском лонг-арифметики ... ну или
в крайнем случае только для само-проверки или теста гипотезы. Вообще сама постановка почему-то
напомнила Числа Грэма.

2) Строки номер (1) и (2). Лексикографически отсортированны это плюс. По крайней мере тривиальные случаи
сравнения работают.

3) Между сроками (3) и (4) разница не-лексикографическая.

4) Надо поискать красивую изящную (возможно рекуррентную формулу) для сравнения
...
Рейтинг: 0 / 0
04.02.2016, 14:49
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163030
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Может логарифмы прикрутить? Если не путаю
Код: sql
1.
log(a^b) = log(a) * b
...
Рейтинг: 0 / 0
04.02.2016, 15:02
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163033
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хм. Если



Тогда я наверное могу переписать табличку так. И осилить почему (9) и (10) строки стоят именно так.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1 2 2 1 1 1
1 2 3 1 1 1
1 3 2 1 1 1
2 2 2 2 1 1
1 3 3 1 1 1
3 2 2 2 2 1
2 4 3 3 1 1
2 2 3 4 1 1
4 2 2 2 2 2
3 3 3 3 3 1
...
Рейтинг: 0 / 0
04.02.2016, 15:04
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163037
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TМожет логарифмы прикрутить? Если не путаю
Код: sql
1.
log(a^b) = log(a) * b


А это мысль. Можно привязаться к монотонности. Тоесть если

A > B

и оба числа очень большие то

ln(A) > ln(B)

также будет справедливо. А сама функция может даст нам возможность чё-нить сократить.
...
Рейтинг: 0 / 0
04.02.2016, 15:06
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163057
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще там подвохи могут быть, типа
Код: sql
1.
3 2 1 2 2


что равно
Код: sql
1.
3 2 1 1 1
...
Рейтинг: 0 / 0
04.02.2016, 15:15
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163112
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Нашел теорему. Возможно будет полезна.

Если a > 1, то неравенство
равносильно неравенству того же смысла: f(x) > g(x). Если 0 < a < 1, то показательное
неравенство равносильно неравенству
противоположного смысла: f(x) < g(x).

В нашем случае основание a либо равно 1 - тогда степени равны (башни одинаковы по рангу)
либо больше единицы (т.к. из условия задачи у нас только целые).
...
Рейтинг: 0 / 0
04.02.2016, 16:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163153
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
думаю, стоит попробовать приводить к виду e^e^e^e^e^e^e^e^e^x
...
Рейтинг: 0 / 0
04.02.2016, 16:27
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163160
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, но как?
...
Рейтинг: 0 / 0
04.02.2016, 16:33
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163206
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

справа налево, каждый раз переходя к новому основанию e.

возможно, идеальным был бы вид x^x^x^x^x^x^x^x^x, но неясно как его получить.
...
Рейтинг: 0 / 0
04.02.2016, 17:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163268
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
если есть n, k>=1, то
n^(k+1)>(n+1)^k
может отсюда как?
...
Рейтинг: 0 / 0
04.02.2016, 18:29
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163348
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonAleksandr Sharahov, но как?
mayton, ты тут кладезь алгоритмов. Напиши, порви студентов. Правда там оценка по количеству букав кода, но время тоже показывается.
...
Рейтинг: 0 / 0
04.02.2016, 20:26
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да какой кладезь? Болото скорее.

Вот если-б Сашик заскочил. Может чё и придумал а у меня кроме логарифмирования идей нет.
...
Рейтинг: 0 / 0
04.02.2016, 21:27
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163514
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
С большой долей вероятности, тут присутствует некое нечёткое сравнение. Быстрая сортировка даёт O(nlnn). Теперь нужно понять сколько времени будет выполняться одна операция сравнения, быстрое возведение в степень + некоторый формат хранения больших чисел, должен дать O(lnn) на одну операцию сравнения, таким образом имеем O(n(lnn)^2). Но всё это нужно очень аккуратно реализовать.

Кроме того, я сильно сомневаюсь в том что существует корректное решение данной задачи, т.к. нечёткое сравнение будет давать погрешность на высоких башнях, значения которых отличаются незначительно. Таким образом,1 вопрос должен быть такой: а можно ли за обозримое время сравнить две девятиэтажных, например, башни ?
...
Рейтинг: 0 / 0
05.02.2016, 09:12
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163516
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
И если процедуру сравнения нельзя провести однозначно, то эта задача неинтересна
...
Рейтинг: 0 / 0
05.02.2016, 09:13
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163524
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
С итоговой оценкой напутал, будет так O(nlgnlga), где n количество чисел, a- максимальное значение коэффициента в башне, что тоже константа, таким образом мы имеем O(nlgn), но на самом деле константа которая находится перед функцией nlgn должна быть скорее всего не меньше 1000
...
Рейтинг: 0 / 0
05.02.2016, 09:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163703
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury, подобного рода задачи (конкурсные, олимпиадные) обычно таят в себе
хинт или подсказку которая позволяет их решить в доступное время (1.5 - 2 часа).
...
Рейтинг: 0 / 0
05.02.2016, 11:42
| Ответить | Цитировать | Написать  
Алгоритмы
    #39163993
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если числа A и B, такие что

Код: sql
1.
2.
A=a1^(a2^a3)....a9
B=b1^(b2^b3)....b9


и все основания и показатели больше либо равны 1 то
я предположил что в данном неравенстве

Код: sql
1.
A < B



можно логарифмировать обе части без потери смысла.



(Поскольку в Latex трудно работать с рядами я взял первые 3 цифры для удобства демонстрации)

получаем произведение с меньшей степенью



еще раз повторил логарифмирование. Раскрыл логарифм произведения.



Степень выражения понизилась но осталась сумма. Как дальше быть - не знаю.
В полном варианте условий у меня еще семь операций.
...
Рейтинг: 0 / 0
05.02.2016, 14:36
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164048
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Есть подозрение что ln(ln(A)) можно просто выкинуть при следующем логарифмировании как незначительную величину.
Как доказать не знаю, думаю как-то исходя из того что ln(ln(99)) < 1
...
Рейтинг: 0 / 0
05.02.2016, 15:08
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164052
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Любая короткая башня легко дополняется единицами до любого требуемого размера.
Потом разворачивается.
Вместо логарифма можно использовать извлечение корня.
В результате получается матрица, которую можно посчитать СЛАУ и стукнуть, например, методом Гаусса.
А вот дальше меня заклинило и критерий сортировки я не смог найти.
...
Рейтинг: 0 / 0
05.02.2016, 15:09
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164199
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonСтепень выражения понизилась но осталась сумма. Как дальше быть - не знаю.


Продолжать )

Нумеровать и вычислять удобнее справа налево:
x=a8^a7^a6^a5^a4^a3^a2^a1^a0;
b0=a0, b1=a1^b0, b2=a2^b1... b8=a8^b7.
Пытаемся свести к вычислению 8-ми вложенных логарифмов
всей башни log(log(log(log(log(log(log(log(x)))))))):
y1=log b1, y2=loglog b2, y3=logloglog b3...
Логарифм суммы вычисляется через произведение
log(u+v)=log(u*(v/u))=loglog u + log(v/u).
Идея в том, чтобы, повторяя это, свести вычисления к предыдущему y
(первое слагаемое) и добавки (второе). Оба небольшие.
...
Рейтинг: 0 / 0
05.02.2016, 16:22
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164212
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovЛогарифм суммы вычисляется через произведение
log(u+v)=log(u*(v/u))=loglog u + log(v/u).
Код: sql
1.
u+v = u*(v/u) = v


?
...
Рейтинг: 0 / 0
05.02.2016, 16:31
| Ответить | Цитировать | Написать  
Алгоритмы
    #39164227
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovЛогарифм суммы вычисляется через произведение
log(u+v)=log(u*(v/u))=loglog u + log(v/u).
Код: sql
1.
u+v = u*(v/u) = v


?

Конечно, опечатка
u+v=u*(1+v/u)
log(u+v)=log(u*(1+v/u))=loglog u + log(1+v/u)
...
Рейтинг: 0 / 0
05.02.2016, 16:39
| Ответить | Цитировать | Написать  
25 сообщений из 208, страница 2 из 9
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]