|
0 / 0 / 0
Регистрация: 03.07.2015
Сообщений: 1
|
|
помогите написать лабу08.09.2009, 15:51. Показов 2999. Ответов 18
Метки нет (Все метки)
1. Дано 36-ричное число, содержащее не более 100 цифр (цифры 10,11,...,35 кодируются заглавными латинскими буквами А,В,...,Z). Переставить цифры числа таким образом, чтобы оно стало "счастливым". "Счастливым" будем называть число из N цифр, у которого сумма первых [N/2] цифр равна сумме последних [N/2] цифр. Если такая перестановка невозможна, вывести сообщение "impossible"
0
|
|
| 08.09.2009, 15:51 | |
|
Ответы с готовыми решениями:
18
Помогите решить лабу. Помогите решить лабу [2] Помогите, умоляю..... нужно сдать лабу..... срочно.... а нифига не получается.... я девушка, сразу поясняю..) |
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
| 09.09.2009, 13:46 | |
|
Посчитать сумму цифр - SUM.
Если SUM нечетное, то сразу ответ - невозможно. Цифры отсортировать по убыванию. Потом перебор 2**N вариантов - нужно выбрать несколько цифр, чтобы их сумма была SUM/2. Тогда остальные невыбранные цифры в сумме тоже будут давать SUM/2. Останется только переставить цифры как требуется.
0
|
|
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
|||
| 09.09.2009, 14:40 | |||
|
Выбирать нужно не несколько цифр, а N/2, не больше, не меньше. Поэтому сортировка бессмысленна. Просто перебор ряда неотсротированных цифр. Задача проста, но... рекурсия. Я попробовал было без рекурсии сделать с десятью значениями, и то плюнул, а тут сто. В данном случае размер кода определяет его сложность.
0
|
|||
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||
| 09.09.2009, 14:53 | ||||
В случае сортированных значений можно сократить перебор. То есть раньше найти нужный вариант.
0
|
||||
|
14 / 14 / 2
Регистрация: 01.02.2009
Сообщений: 23
|
|
| 09.09.2009, 15:18 | |
|
Тут пример есть этой задачи. Я утром пытался сделать но так и не получилось...
http://www.kursovik.com/programming/101003.html
0
|
|
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
|
| 09.09.2009, 15:36 | |
|
Ладно, давайте так.
Имеем ряд чисел. Допустим, их 10 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 Согласны вы со мной в том, что чтобы найти правильное решение, необходимо будет перебрать такие значения x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 x0, x1, x2, x3, x4, x5, x6, x7, x8, x9 ...Это далеко не конец. И так далее. То есть, перебрать ВСЕ пятёрки? Рискну предположить, что согласны. И сразу: если это так, до для того, чтобы найти все решения задачи, придётся рассмотреть все пятёрки чисел, что в отсортированном, что в неотсортированном массиве. А вот если необходимо будет найти одно решение, то в самомо общем случае с отсортированном массивом работы будет больше. Ибо сперва будут рассматриваться первых 5 чисел.А их сумма больше последующих пяти безусловно- массив-то отсортиован. То есть где-то если решение сущесвует, где-то в середине такого вот перебора вы его найдёте. А может, и в конце. А в неотсортированном на правильное решение можно натолкнуться когда угодно. Но это был вопрос по сортировке. А теперь: ...Вы по-прежнему не хотите использовать рекурсию? Можно, кто же спорит...Но соловья баснями не кормят. Я дам вариант с рекурсией. Что касается варианта без рекурсии, то в исходнике должно быть 50 циклов, вложенных один в другой. Далее, не факт, что чисел-то будет 100! А это значит, что сумма N/2 чисел может подсчитываться не в теле самого последннего, внутреннего цикла, но и в телах остальных 49 циклов... И всё это надо описать... Нет, уж увольте. Или я не прав?
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 09.09.2009, 20:16 | |
|
Если еще совсем не опоздал то ответьте. Я могу написать необходимую Вам программу.
0
|
|
|
0 / 0 / 0
Регистрация: 03.07.2015
Сообщений: 1
|
|
| 10.09.2009, 16:12 | |
|
нет, не опоздал!!я только за!!))
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
|||||
| 10.09.2009, 17:02 | |||||
Полный перебор - это то чего хочешь сделать ты. Но есть разные методы сократить полный перебор. В частности если отсортировать массив, что можно сократить число вариантов. Пусть например x0==100, x1==100, а остальные xi сильно меньше. Тогда при переборе все варианты когда выбрано и x0 и x1 не годятся для решения. В частности все варианты которые ты написал в посте вообще не следует перебирать ![]()
Единственная здравая мысль
0
|
|||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
| 10.09.2009, 19:27 | ||||||
|
Ну вот вроде бы все:
0
|
||||||
|
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
|
|||
| 11.09.2009, 18:00 | |||
|
Добавлено через 5 минут стоит или нет использовать рекурсию лучше обсудить когда появится приемлимый по времени выполнения алгоритм данная задача задавалась в учебнике ахо ульмана алгоритмы и структуры данных, с максимальным рейтингом сложности, может стоит где поискать ответы с подсказками решений?
0
|
|||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
| 12.09.2009, 16:38 | ||||||
|
_mayor,
Каюсь, писал после 2-х л пива, а накануне был 1 л водки. Теперь написал на трезвую голову. Проверял работает и с числами под 100 цифр.
0
|
||||||
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
||||||||||||||||||||||
| 13.09.2009, 05:40 | ||||||||||||||||||||||
|
...Тем не менее, других алгоритмов я не вижу. А некоторые остряки штатские видят, но молчат с умным видом. Дескать, знаем, но не скажем. Пусть реализую формулировку "остальные xi сильно меньше". (odipовский перл) тогда и будем говорить. Но слоловья баснями не кормят. Короче, вот моё НЕПОЛНОЕ решение с рекурсией.
Как- это пусть тредстартер думает. Далее, если чисел нечётное число или их сумма нечётна, написать, что решения нет. Теперь нужно прописать количество чисел. Это может сделать программно, подсчитав их, можно вручную. В моём примере это сделано в макросе
Для тредстартерского примера его начальное значение равно kolichestvo_chisel/2 То есть половина будет. Если чисел 40, то половина будет 20. Эта функция выдаёт на гора все суммы пятёрок, шестёрок- двадцаток и так далее, кто что пожелает. Задача тредтстартера ВРУЧНУЮ найти половину (SUM) суммы и каждый раз сравнивать выведенную сумму с SUM. Предварительно сохранив номера элементов массива stroka. Допустим, однажды суммы сравнялись. Ага, номера известны. Теперь заполняй новый массив последвательно элементами с такими нормеами, и потом с оставшимися номерами. Это всё автор пусть сам делает. ...Ну, а моя функция работает так. Каждый раз в функции рассматривается ПОДМАССИВ последовательно идущих чисел и ищется его сумма. Допустим, массив чисел такой 12, 34, 56, 67, 34, 56, 100, 12, 45, 100, 23, а подмассив такой 12, 34, 56, 67, 34, 56, 100, 12, С помощью нехитрых манипуляций вызывается рекурсивно эта же функция, работающая уже с таким подмассивом 34, 56, 67, 34, 56, 100, 12, потом с таким 56, 67, 34, 56, 100, 12, и так далее, пока не останется число 12. Теперь к сумме последовательно прибавляется и отнимается число 12, потом 45, 100 и 23 Следующий расассматриваемый подмассив будет (благодаря циклу) 100, 12 Вот так по функциям проходим и ищем сумму. Ну, там ещё каждый раз функция принимает служебные аргументы- номер функции, номер элемента (имеется ввиду индекс в stroka) и сколько элементво осталось прибавить. Автор, вопрос на соображение. И всем тоже. Значит, задача поставлена, условие известно. Если решение есть (что не факт), я могу со стопроцентной вероятностью указать одно его число. Не примерно, не скорее всего, а именно 100 процентов, что это число (шестнадцатиричная цифра) будет присутствовать в ответе. Какое это число? Ну, всё, пока. P. S. Предыдущий алгоритм представлял бы интерес с комментариями какими-нибудь, что ли...
0
|
||||||||||||||||||||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 13.09.2009, 08:07 | |
|
Комментарии к предыдущему алгоритму:
1. Заносим значения каждой цифры введеного числа в массив mas_ch[] в десятичной форме (для этого используем созданный массив mas_36[]). 2. Проводим (проверку на то что количество цифр четное и что сумма цифр делится без остатка на 2). 3. Вычисляем сумму элементов (она нам нужна , т.к. в дальнейшем алгоритм построен таким образом: необходимо выбрать половину цифр, чтобы их сумма была равна половине суммы). 4. С помощью стека делаем перебор элементов (стек создан размером = половина количества цифр начального числа).(В дальнейшем я пишу "сумма цифр в стеке", это для простоты. На самом деле в стеке находятся индексы элементов массива mas_ch[] и я подразумеваю под суммой цифр в стеке - сумму элементов массива mas_ch[] индексы которых находятся в стеке) В общих чертах перебор выглядит так (перебор выполняем до тех пор пока первым элементом в стеке не окажется индекс цифры массива mas_ch[]) который = половина количества цифр массива mas_ch[] + 1): Заносим число в стек. Входим в цикл. Первая проверка: если стек заполнен и сумма цифр стека равна половине суммы цифр массива mas_ch[], то выходим из цикла. Вторая проверка: если в стеке последний индекс массива mas_ch[] и сумма цифр стека не равна половине суммы цифр массива mas_ch[], то удаляем из стека подряд идущие индексы, затем еще один и вместо последнего в стек заносим следующий за ним. (При первом прохождении цикла эта проверка не нужна, но нужна при последующих прохождениях). Третья проверка: ((если стек заполнен, а сумма цифр стека не равна половине суммы цифр массива mas_ch[]) или (стек не заполнен, а сумма превышена)) и не достигнут последний индекс массива mas_ch[], то последний индекс массива mas_ch[] в стеке заменяем на следующий. Четвертая проверка: если стек не заполнен и сумма цифр стека не превышает половины суммы цифр массива mas_ch[], то заносим в стек следующий индекс массива mas_ch[]. В конце цикла нахожу сумму цифр стека. После цикла еще одна проверка на счастливость и вывод результата (с переводом десятичных чисел в 36-ричные).
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||
| 13.09.2009, 10:19 | ||
0
|
||
|
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
|
|
| 13.09.2009, 12:55 | |
|
valeriikozlov, переменная LIFO что означает?
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 13.09.2009, 13:09 | |
|
Переменная LIFO (массив) является стеком
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 18.09.2009, 17:14 | |
|
evlan,
А вы внимательно прочитайте условие задачи. Кстати я в начале задачи поставил проверку на не превышение 100 символов, так что ввести 100 символов и более Вам не удастся.
0
|
|
| 18.09.2009, 17:14 | |
|
Помогаю со студенческими работами здесь
19
Помогите написать лабу!! ПОМОГИТЕ СДЕЛАТЬ ЛАБУ Помогите сделать лабу на тему простые разветвления
Помогите написать формулу ,никак немогу написать (2k)! в ней Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога
Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
|
Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm)
8Observer8 30.01.2026
Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .
|
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
|
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования.
Часть библиотеки BedvitCOM
Использованы. . .
|
|
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога
SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
|
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога
SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
|
Влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
|
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога
SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
|