ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
25 сообщений из 339, страница 13 из 14
  13  все
Относительно простые задачки
    #39940327
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
Aleksandr Sharahov, так хорошо в надежде, что не все варианты нужно перебрать. Но умозрительно кажется, что придётся рассматривать фиктивные варианты. Т.к. если обратный вывод, то мы не знаем заранее, какой угол получен на пересечении бисектриссы со стороной, а какой делением угла и т.д.
Ну т.е. кроме равенства А+В+С=180 и нечем воспользоваться, выходит.


Требуемое финальное состояние с отношением углов 1:3:5 может быть получено
только из трех предыдущих состояний: 1:2:6, 2:2:5, 2:3:4.

Эти три состояния, в свою очередь, могут быть получены только из состояний:
1:2:6, 1:4:4, 2:2:5, 2:3:4.

Состояние 1:4:4 может быть получено только из 2:3:4.

Видим, что среди всех возможных начальных состояний нет финального.
...
Рейтинг: 0 / 0
23.03.2020, 18:04
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39940399
labarad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
labarad
Гость
Имя пользователя1
классический реверс дает 49 обменов символами (первый с последним, второй с предпоследним и тд), он по любому быстрее. Здесь прикол именно в ограничениях - можно обменивать местами только соседние подстроки

Наверное, всё-таки предпочту сдаться. Если было бы очень нужно , то решал бы задачу методом перебора на 9 или 10 элементах: количество символов+начальная позиция дают N во второй степени итераций для шага. А таких шагов по условию задачи д.б. не более, чем N/2+1. Т.е. для 10 элементов в худшем случае порядка триллиона операций (10 в 12-ой), чтобы увидеть незамечаемое.
...
Рейтинг: 0 / 0
23.03.2020, 22:08
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39940485
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
labarad,

все украдено до нас:
https://www.researchgate.net/publication/8007399_An_Efficient_Algorithm_for_Sorting_by_Block-Interchanges_and_Its_Application_to_the_Evolution_of_Vibrio_Species
...
Рейтинг: 0 / 0
24.03.2020, 11:33
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941125
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
У меня рекорд вчера был 6 перестановок для (1 2 3 4 5 6 7 8). Но воспроизвести не смог, т.к. перемещал по столу фишки из коробки "Пятнашки" и не записал.

А с бисектриссами, да, воспроизвёл. Действитеьлно невозмоно получить. Оказалось, что эту задачу быстрее было 1 раз сделать, чем 100 раз думать, как это сделать. Такая мораль.
...
Рейтинг: 0 / 0
25.03.2020, 22:44
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941137
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98
У меня рекорд вчера был 6 перестановок для (1 2 3 4 5 6 7 8). Но воспроизвести не смог, т.к. перемещал по столу фишки из коробки "Пятнашки" и не записал.


и эта тоже не особенно сложная, сама формула намекает, что надо работать с парами )
...
Рейтинг: 0 / 0
26.03.2020, 00:01
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941161
labarad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
labarad
Гость
exp98
У меня рекорд вчера был 6 перестановок для (1 2 3 4 5 6 7 8). Но воспроизвести не смог, т.к. перемещал по столу фишки из коробки "Пятнашки" и не записал.

Если Вы про строку в 99 символов, тогда точно надо прогу написать. Хотя в оценке количества итераций я и ошибся (помимо начальной позиции и общего количества символов ещё есть разделитель), но с 8-ю элементами прога посчитает в обозримое время. Ну а как только уловка станет видна, воспроизвести её на большем масштабе не составит труда.
...
Рейтинг: 0 / 0
26.03.2020, 04:03
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941194
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
labarad
exp98
У меня рекорд вчера был 6 перестановок для (1 2 3 4 5 6 7 8). Но воспроизвести не смог, т.к. перемещал по столу фишки из коробки "Пятнашки" и не записал.

Если Вы про строку в 99 символов, тогда точно надо прогу написать. Хотя в оценке количества итераций я и ошибся (помимо начальной позиции и общего количества символов ещё есть разделитель), но с 8-ю элементами прога посчитает в обозримое время. Ну а как только уловка станет видна, воспроизвести её на большем масштабе не составит труда.


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

Для обратной перестановки программа не нужна, т.к. есть регулярный алгоритм с точно известным количеством шагов.
Чтобы понять, что к чему, проще начать с нечетного N=5, 7, 9, 11, 13, например, на картах.
...
Рейтинг: 0 / 0
26.03.2020, 09:16
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941789
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Немного оффотоп, тем не менее.
Относительно простые задачки в игре exapunks , много кто решал? Игра про конечные автоматы, с завуалированными ограничениями на количество используемых регистров. В торренте - лежит.Задачи простые, но вопрос о другом - кто-нибудь пробовал? Язык как бейсик команд 20, и все интуитивные.
Меня зацепило уже месяц ковыряю расслабленно под настроение. Задачи, они не просто на математику, а на прикладное программирование что ли.
Отдельный вопрос графики в сравнении с остальными вот бы где спорщиков по датабаза круче и чей язык быстрее протестировать.
Наберите exapunks в ютубе, может кому приглянется, у кого зуд этот, чтоб его, чего-то покодить.
...
Рейтинг: 0 / 0
27.03.2020, 20:47
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941846
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Сам себе на уме тихо веду монолог...
авторОтдельный вопрос графики в сравнении с остальными
RTFM :D :D :D Изучал графики, похоже они твои же предыдущие попытки просто отрисовывают :D В ютубах тоже неоднократно встречал подобное моему заблуждение :D Взял из первых обучающих заданий программу, и в хвост ее и в гриву, там просто не может быть более изящного решения, только тогда обратил внимание, чтоже графики по завершению показывают, до этого никак.
zachtronics молодцы, у меня ощущение, что все шишки зазвидевшемуся "программисту" на одном блюде вынесли :D

Не сочтите за рекламу, но раз тема про относительно простые задачи - ВЕЩЬ EXAPunks Zachtronics, уже в торрентах :D
...
Рейтинг: 0 / 0
28.03.2020, 11:03
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39941980
АСУ ТПшник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АСУ ТПшник
Участник
Вчера были гости дома, обсуждали детей, пока они в других комнатах в телефоны играли.
Тут меня осенило - пойдем Миша попробуем эту игру.
Вердикт- с алгоритмикой у него все замечательно, но не его это от слова вообще. Т.е. на простые действия он разложить может, а вот то, что робот делает все строго по его указке (я команды тупо набивал что он скажет на обучающем уровне), его никак не вставило. Очень полезная игра.
...
Рейтинг: 0 / 0
29.03.2020, 11:41
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39991983
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
по программированию:

гирьки произвольной массы выставлены в ряд. Определить, какую максимальную суммарную массу мы сможем составить из гирек, при условии, что никакие две соседние гирьки использовать одновременно нельзя.

время O(N), память O(1)

пример: гирьки 5, 3, 7, 9, 1, результат 14 (взяли гирьки 5 и 9)
...
Рейтинг: 0 / 0
24.08.2020, 14:35
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39991984
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
по математике:

Два человечища играют в числа: первый называет некоторое натуральное число, второй вычитает целый квадрат из названного, далее, по очереди - первый возводит оставшееся значение в натуральную степень, второй вычитает какой-нибудь целый квадрат, и т.д. Второй выигрывает, когда число обнулится (как сами знаете кто). Может ли первый не допустить обнуления?
...
Рейтинг: 0 / 0
24.08.2020, 14:40
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992047
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Имя пользователя1
... Определить, какую максимальную суммарную массу мы сможем составить из гирек, ...

составить из 2-х гирек ??
...
Рейтинг: 0 / 0
24.08.2020, 18:44
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992070
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
exp98
Имя пользователя1
... Определить, какую максимальную суммарную массу мы сможем составить из гирек, ...

составить из 2-х гирек ??
это в примере получилось из 2х, потому что их всего 5.
а так гирек может быть много, и соответственно выбрать получится много. Главное, чтобы выбранные не стояли изначально рядом друг с другом
...
Рейтинг: 0 / 0
24.08.2020, 20:18
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992163
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
по программированию:

гирьки произвольной массы выставлены в ряд. Определить, какую максимальную суммарную массу мы сможем составить из гирек, при условии, что никакие две соседние гирьки использовать одновременно нельзя.

время O(N), память O(1)

пример: гирьки 5, 3, 7, 9, 1, результат 14 (взяли гирьки 5 и 9)
С двумя гирьками все просто
Код: pascal
1.
2.
3.
4.
5.
6.
MaxL := X[0];
Result := X[2] + MaxL;
for i := 1 to N - 3 do begin
  MaxL := Max(MaxL, X[i]);
  Result := Max(Result, X[i+2]+MaxL);
end;

Для произвольного числа, вероятно нужно обобщить - считать условные "Odd" и "Even" суммы слева и выбирать, что пристыковать к результату.
...
Рейтинг: 0 / 0
25.08.2020, 10:49
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992167
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
по математике:

Два человечища играют в числа: первый называет некоторое натуральное число, второй вычитает целый квадрат из названного, далее, по очереди - первый возводит оставшееся значение в натуральную степень, второй вычитает какой-нибудь целый квадрат, и т.д. Второй выигрывает, когда число обнулится (как сами знаете кто). Может ли первый не допустить обнуления?
Думаю, что да.
Поскольку ряд сумм квадратов натуральных чисел расходится, всегда найдется такая степень k (нечетная, разумеется), что число при вычитании ближайшего квадрата будет а) больше результата предыдущей итерации б) не являться квадратом натурального числа.
...
Рейтинг: 0 / 0
25.08.2020, 10:51
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992186
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Имя пользователя1
по математике:

Два человечища играют в числа: первый называет некоторое натуральное число, второй вычитает целый квадрат из названного, далее, по очереди - первый возводит оставшееся значение в натуральную степень, второй вычитает какой-нибудь целый квадрат, и т.д. Второй выигрывает, когда число обнулится (как сами знаете кто). Может ли первый не допустить обнуления?
Думаю, что да.
Поскольку ряд сумм квадратов натуральных чисел расходится, всегда найдется такая степень k (нечетная, разумеется), что число при вычитании ближайшего квадрата будет а) больше результата предыдущей итерации б) не являться квадратом натурального числа.
идея не совсем верная.

может, я криво сформулировал?
ходы первого и второго на псевдокоде с присваиваниями выглядят так:

1) X := ...
2) X := X - n 2
1) X := X m
2) X := X - n 2
1) X := X m
...
всё кроме первой строки повторяется, n и m на каждой итерации произвольные (не обязательно одни и те же).
...
Рейтинг: 0 / 0
25.08.2020, 11:40
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992195
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Пока не cxbnfk.
Если может, то 1-му надо не допустить, чтобы при его ходе
1) Y := X^m
X было квадратом. Тогда m можно брать нечётным.

С другой стороны, 2-й всегда может дать приближение к Y с точностью(2n+-1), т.к. (n+1)^2= n^2 +2n+1
...
Рейтинг: 0 / 0
25.08.2020, 12:06
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992197
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1,
Вроде я так и понял.

Первому игроку нужно не допустить чтобы
X m -n 2 =k 2 ,
а поскольку нет ограничений на m, это без труда можно сделать.
...
Рейтинг: 0 / 0
25.08.2020, 12:09
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992205
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис,

в общем, решение пока не верное)
...
Рейтинг: 0 / 0
25.08.2020, 12:32
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992206
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
exp98
С другой стороны, 2-й всегда может дать приближение к Y с точностью(2n+-1), т.к. (n+1)^2= n^2 +2n+1
как это использовать?
...
Рейтинг: 0 / 0
25.08.2020, 12:32
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992207
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Для произвольного числа, вероятно нужно обобщить - считать условные "Odd" и "Even" суммы слева и выбирать, что пристыковать к результату.
да, тут можно выбирать произвольное число гирек, понятно что чем больше тем лучше.
например, если все гирьки одинаковы, то просто берем все нечетные, это будет половина или чуть более (если гирек нечетное количество)

сама задачка не сказать что интересная, но здесь прикольно что решение совсем простое
...
Рейтинг: 0 / 0
25.08.2020, 12:35
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992209
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
С гирьками поэкспериментировал... Написать NlogN легко, а чтобы именно что N было..

У меня были примеры рандома когда выбиралась гирька с нулевым весом (чтобы это ни значило), потому что ее соседи мешали взять что-то тяжелое... И много случаев, когда самая тяжелая гирька не используется.


С квадртами я пока дошел до мысли что можно сделать число четным, потом сделать число кратным тройке, потом пятерке, только смысла в этом немного... Разве что произведение простых чисел минус один в определенный момент станет квадратом.
Тогда как первый ни возводи в степень этот квадрат, ничего не выйдет.
...
Рейтинг: 0 / 0
25.08.2020, 12:43
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39992289
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aklin
И много случаев, когда самая тяжелая гирька не используется.
да запросто, например (2, 3, 2)
...
Рейтинг: 0 / 0
25.08.2020, 14:54
| Ответить | Цитировать | Написать  
Относительно простые задачки
    #39993728
982183
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
982183
Участник
Я правильно понимаю, что простой перебор вариантов считается "неспортивным" способом?
...
Рейтинг: 0 / 0
29.08.2020, 08:01
| Ответить | Цитировать | Написать  
25 сообщений из 339, страница 13 из 14
  13  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Относительно простые задачки
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39992047&tid=1339678]:
 0ms
get settings:
 11ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 161ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 68ms
get tp. blocked users:
 1ms
others: 14ms
total:  286ms
созд. / загр.: 286ms
x
x
Закрыть


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