Необходим алгоритм конкурса разработчиков
Привет коллеги разработчики я участвую в конкурсе разработчиков в моем округе, и у меня есть практические задания для экзамена, я был успешен с большинством из них, однако у меня возникли проблемы с этим, в частности, не могли бы вы взглянуть любые идеи или помощь приветствуются, язык программирования не имеет значения, он может быть решен на любом языке, вот задача:
Есть арифметическая прогрессия, написанное на черной доске. Не имея ничего лучшего, вы придумали игру, включающую его. А именно, вы стираете все четные числа и заменяете их числами в два раза меньшими.
Вы повторяете эту процедуру до тех пор, пока на доске не останется четных чисел.
Например, вы трансформируете прогрессию {1, 2, 3, 4, 5, 6} в {1, 1, 3, 2, 5, 3} а потом еще раз в {1, 1, 3, 1, 5, 3}.
Когда приходят ваши друзья,вы просите их угадать первоначальную прогрессию.
напр.
Давайте возьмем прогрессию 6, 5, 4, 3, 2, 1
На первом этапе он становится 3, 5, 2, 3, 1, 1
Тогда она становится 3, 5, 1, 3, 1, 1
Это означает для чисел 3, 5, 1, 3, 1, 1 решение таково 6, 5, 4, 3, 2, 1, в результате получается сумма 21.
Входной параметр:
прогрессия-массив целых чисел, представляющих исходную прогрессию после
все числа были сведены к нечетным элементам
Ограничения:
Число элементов в прогрессии составляет от 4 до 500 включительно.
Каждый элемент прогрессии составляет от 1 до 1000000 включительно.
Все элементы прогрессии нечетны.
Значение:
Сумма элементов исходной арифметической прогрессии
Если существует более одного решения, верните то, которое имеет меньшую сумму всех элементов.
Обратите внимание, что всегда будет решение, где каждое число исходной прогрессии меньше 1000000.
имя класса:
Развитие
Подпись метода:
public int reverse (int[] прогрессия)
СЦЕНАРИИ ТЕСТИРОВАНИЯ
Тестовый случай 1: обратный({1, 1, 3, 1, 5, 3}) = 21
Тестовый случай 2: обратный({1, 1, 1, 1, 1, 1}) = 6
Тестовый случай 3: обратный({3, 3, 3, 3}) = 12
Тестовый случай 4: обратный({3, 5, 1, 3, 1, 1}) = 21
Тестовый случай 5: обратный({21, 27, 33, 39, 45, 51}) = 216
Тестовый пример 6: реверс({37, 15, 23, 1, 9, 1}) = 117
Тестовый случай 7: обратный({1019, 1077, 1135, 1193, 1251, 1309, 1367, 1425, 1483, 1541}) = 12800
Тестовый пример 8: реверс({1103, 2067, 241, 1789, 825, 1511, 343, 1233, 547, 955, 51, 677, 269, 399, 65, 121}) = 18616
Тестовый случай 9: обратный({5, 5, 5, 5, 5}) = 25
Тестовый случай 10: обратный({5, 1, 11, 7, 17}) = 55
Что я уже пробовал:
Сначала я попробовал, когда все элементы в массиве одинаковы, просто вернуть их сумму, и я делаю еще один массив с разницей всех элементов от первого, и если второй массив имеет все те же элементы, просто вернуть их сумму. Я понятия не имею для других тестовых случаев, какое число должно быть умножено на два, а какое нет.
PIEBALDconsult
Интересно, что ваша программа будет делать с:
1 , 1 , 1 , 3 , 5 , 1 , 13 , 21 , 17 , 55
(Исправленный. Но теперь я вижу, что это арифметический ряд, а не арифметическая последовательность.)
MarijaMKBT
Я понятия не имею. Если мне удастся написать правильный алгоритм, который правильно решает все тестовые случаи, мы тоже можем попробовать ваш пример. Спасибо,что опубликовали это.
Patrice T
Насколько я понимаю, это невозможно.
PIEBALDconsult
Это не то, что я, вероятно, попробую сам.
Patrice T
Мне любопытно увидеть решение, потому что просто 1, 1, 1, 3 не могут привести к арифметической прогрессии.
PIEBALDconsult
(Фибоначчи)
Patrice T
Ладно, понятно, значит, это не арифметическая прогрессия.
Я следую за вами до 21 года, но сомневаюсь насчет 11 и 75.
PIEBALDconsult
Это прогрессия, если только фактическая спецификация не имеет четкого определения "прогрессии".
Вполне возможно, что я облажался, я могу еще раз проверить свою работу.
Patrice T
"арифметическая прогрессия" довольно хорошо определена.
PIEBALDconsult
Насколько я могу судить, нет, особенно если учесть, что спецификация включает в себя регрессионные значения.
И да, я все испортил - обновлю список выше.
PIEBALDconsult
Теперь, когда я взглянул на это по-новому, я рекомендую посмотреть только на первые четыре значения в последовательности-из них вы можете восстановить всю последовательность.
Но все, что вам действительно нужно сделать, это определить значение нулевого элемента и значение, которое добавляется на каждом шаге-остальное простая математика.