ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
25 сообщений из 208, страница 6 из 9
  6  все
Алгоритмы
    #39167112
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
log 2 (2 7 ) = 7
...
Рейтинг: 0 / 0
09.02.2016, 20:45
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167115
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovDima T,

логарифм по основанию 2 наибольшего значения этажа к наименьшему
log 2 (10) = 1,008600172
Это меньше, но откуда родилось данное утверждение?
...
Рейтинг: 0 / 0
09.02.2016, 20:48
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167118
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Логарифм по основанию 2 отношения наибольшего значения этажа к наименьшему берется отсюда.
Пусть b1=7 * b2
Тогда 2^b1 = 2^(7*b2) = (2^7)^b2 = 128^b2 > 99^b2,
2^2^b1 = 2^128^b2 > 99^99^b2, т.к. даже при b2=2 имеем 2^128^2 = 2^16k = (2^16)^1024 > 99^1000
ну и т.д.
...
Рейтинг: 0 / 0
09.02.2016, 20:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167124
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
7 это log(2,99) с некоторым запасом.
Можно доказать, что чем больше значения сравниваемых шапок, тем меньший запас нужен.
Т.е. как отношение шапок за 7 перевалило, так уже точно башня с большей шапкой больше.
...
Рейтинг: 0 / 0
09.02.2016, 21:00
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167202
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr Sharahov2^2^b1 = 2^128^b2 > 99^99^b2, т.к. даже при b2=2 имеем 2^128^2 = 2^16k = (2^16)^1024 > 99^1000


тут неточность

2^2^b1 = 2^128^b2 > 99^99^b2, т.к. даже при b2=2^2^2 имеем 2^128^16 > 99^99^16 и снова (128/99)^16 > 7
и т.д.
...
Рейтинг: 0 / 0
10.02.2016, 01:01
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167210
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Берите натуральный. У него больше возможностей к преобразованиям.
...
Рейтинг: 0 / 0
10.02.2016, 01:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167426
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
А как вычисляют, что например
2^2^65536~10^10^21840?

Взято отсюда .
...
Рейтинг: 0 / 0
10.02.2016, 11:55
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167487
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ЕвгенийВА как вычисляют, что например
2^2^65536~10^10^21840?

Взято отсюда .

lglg(2^2^65536) = lg(2^65536*lg2) = 65536*lg2+lglg2 ~ 19728
значит 2^2^65536 ~ 10^10^19728
...
Рейтинг: 0 / 0
10.02.2016, 12:42
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167587
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Aleksandr Sharahovзначит 2^2^65536 ~ 10^10^19728
Значит там ошибка?
19728, а не 21840?
...
Рейтинг: 0 / 0
10.02.2016, 13:51
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167610
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
maytonНу нет там такого. Смотри внимательнее. Под логарифмом - сумма. В последнем преобразовании.
Дальше просто не было преобразований.

Будь осторожнее с такими аналогиями. Конешно область определения уходит в минус.
Но твоя формула не равна моей.
В моём первом варианте преобразований надо уйти от неопределённостей.
Например сдвинуть логарифму на 1 влево (или прибавить +1 к аргументу под логарифмом)

http://yotx.ru/#!1/3_h/ubWwf7Wwf7Rgzhf23/aP9g/2DfT0qt7RPgG3vQrd39g30SDbuxc8p4PN1iPG5dXuzub@0DBg==
...
Рейтинг: 0 / 0
10.02.2016, 14:13
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167614
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Четыре преобразования и всё ОК. Без выхода в отрицательную область определения.

y = ln(ln(ln(ln(x+1)+1)+1)+1)
...
Рейтинг: 0 / 0
10.02.2016, 14:16
| Ответить | Цитировать | Написать  
Алгоритмы
    #39167639
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
ЕвгенийВAleksandr Sharahovзначит 2^2^65536 ~ 10^10^19728
Значит там ошибка?
19728, а не 21840?

Человеку свойствинно ошебаться ))
...
Рейтинг: 0 / 0
10.02.2016, 14:37
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168792
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я решил

 
Описание алгоритма
1. Нормализовать верхи башень, т.е. считать верхи пока считаются, например 2^(2^(2^(2^2))) привести к 2^65536
2. Сравнивать три верхних уровня: ln(ln(a 3 )) + ln(a 4 ) * a 5 и ln(ln(b 3 )) + ln(b 4 ) * b 5
3. Если верхи совпали - сравнивать нижние сверху вниз: a 2 и b 2 если равны a 1 и b 1
...
Рейтинг: 0 / 0
11.02.2016, 16:55
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168808
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima T,
Сравни по своему алгоритму
99, 99, 78, 98, 99, 90, 99, 99
25, 34, 99, 75, 2, 99, 99, 92, 99
...
Рейтинг: 0 / 0
11.02.2016, 17:07
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168815
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TЯ решил

 
Описание алгоритма
1. Нормализовать верхи башень, т.е. считать верхи пока считаются, например 2^(2^(2^(2^2))) привести к 2^65536
2. Сравнивать три верхних уровня: ln(ln(a 3 )) + ln(a 4 ) * a 5 и ln(ln(b 3 )) + ln(b 4 ) * b 5
3. Если верхи совпали - сравнивать нижние сверху вниз: a 2 и b 2 если равны a 1 и b 1


B 18783990 тот же самый алгоритм сравнения )
...
Рейтинг: 0 / 0
11.02.2016, 17:11
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168828
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
99, 99, 78, 98, 99, 90, 99, 99 < 25, 34, 99, 75, 2, 99, 99, 92, 99

Если кому сравнить - пишите, посчитаю, только запросы оформляйте в формате тестов
Код: sql
1.
2.
3.
2
7 99 99 78 98 99 90 99 99
8 25 34 99 75 2 99 99 92 99


Ответ
Код: sql
1.
1 2
...
Рейтинг: 0 / 0
11.02.2016, 17:21
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168838
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima T,
9 99
27 66
...
Рейтинг: 0 / 0
11.02.2016, 17:31
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168845
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
Алгоритм сравнения сразу правильный придумали 18772992 18773013 18777841

Но одного алгоритма сравнения мне не хватило. Думаю он не срабатывает из-за погрешностей логарифмирования на каких-то башнях с очень близкими значениями.
...
Рейтинг: 0 / 0
11.02.2016, 17:38
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168849
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima T,
9 99
27 66
они равны, что противоречит условию задачи.
...
Рейтинг: 0 / 0
11.02.2016, 17:41
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168855
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
ты тут перемудрил
Код: sql
1.
abs(x1-x2)/(abs(x1)+abs(x2)+epsilon)>epsilon


затестил ради интереса - не проходит мой код с такой проверкой.
у меня проще
Код: sql
1.
abs(x1-x2)>epsilon
...
Рейтинг: 0 / 0
11.02.2016, 17:50
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168859
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TAleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
Алгоритм сравнения сразу правильный придумали 18772992 18773013 18777841

Но одного алгоритма сравнения мне не хватило. Думаю он не срабатывает из-за погрешностей логарифмирования на каких-то башнях с очень близкими значениями.

Да, это понятно.

Но вся суть алгоритма в том, чтобы различать почти одинаковые башни (k<7),
при этом отбраковывая одинаковые.

Дело в том, что таких башен конечное число, и, похоже, что после склейки верхних уровней
не существует таких башен высотой более 4 (если считать склеенные уровни за 1).
Т.е. главная фишка алгоритма - именно склейка верхних уровней.
...
Рейтинг: 0 / 0
11.02.2016, 17:52
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168866
Фотография ЕвгенийВ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ЕвгенийВ
Участник
Dima TЕвгенийВDima T,
9 99
27 66
они равны, что противоречит условию задачи.
нет равных разве не подразумевает например 2 3 2 и 2 3 2?
...
Рейтинг: 0 / 0
11.02.2016, 17:58
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168878
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ЕвгенийВDima Tпропущено...

они равны, что противоречит условию задачи.
нет равных разве не подразумевает например 2 3 2 и 2 3 2?
Думаю что нет. Мой код на
Код: sql
1.
2.
9 99
27 66

и на
Код: sql
1.
2.
27 66 
9 99


дает ответ
Код: sql
1.
1 2


но ответ
Код: sql
1.
2 1


тоже правильный, что вызывает неопреденность.
...
Рейтинг: 0 / 0
11.02.2016, 18:04
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168926
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr SharahovДело в том, что таких башен конечное число, и, похоже, что после склейки верхних уровней
не существует таких башен высотой более 4 (если считать склеенные уровни за 1).
Т.е. главная фишка алгоритма - именно склейка верхних уровней.
c 10 до 4 не склеить даже если там одни двойки. 2^2^2^2 = 65536 а дальше не склеить.

Но т.к. по условию задачи исходные уровни не более 99, т.е. максимум склеиваются три верхних в один, например 2^2^2 = 16
Как следствие функция проверки должна работать без склеивания. А если она не работает, то значит должна существовать такая пара пятиуровневых башень A(a1^a2^a3^a4^a5) и B(b1^b2^b3^b4^b5) удовлетворяющих условию A<B при
a3^a4^a5>b3^b4^b5 или (a3^a4^a5=b3^b4^b5 и a2>b2) или (a3^a4^a5=b3^b4^b5 и a2=b2 и a1>b1)

Ломаю голову как найти такую комбинацию, т.е. доказать что без склейки никак не решить. Перебор тут на годы может растянуться.
...
Рейтинг: 0 / 0
11.02.2016, 18:43
| Ответить | Цитировать | Написать  
Алгоритмы
    #39168940
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ЕвгенийВDima TДля практики можешь задачки олимпиадные порешать.
Оффтоп!
чета я в условия этой не въеду.
Редиска ты, Евгений.

Ты отсортировал задачи по сложности в выдал нам самую топовую из всех 700
http://acmp.ru/index.asp?main=tasks&str= &page=13&id_type=0

Ну неужели не мог найти чё-нить поприятнее ну йо-майо.
...
Рейтинг: 0 / 0
11.02.2016, 18:58
| Ответить | Цитировать | Написать  
25 сообщений из 208, страница 6 из 9
  6  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмы
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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