Найти самую "красивую" последовательность, состоящую из N чисел

@kate_sam · Регистрация: 25.11.2018

Author24 — интернет-сервис помощи студентам

Не могу решить эту задачу уже 3 дня, не понимаю в чем логика, может быть кто-то догадается и сможет мне объяснить ?)

Задача №1850. Красивая последовательность

Красотой последовательности состоящей из N натуральных чисел, будем называть минимальное натуральное число M, не представимое в виде алгебраической суммы некоторых элементов данной последовательности. Например, красота последовательности 2,3,4 равна 8 (1=−2+3, 2=−2+4, 3=3, 4=4, 5=2+3, 6=2+4, 7=4+3, 8=?). Напишите программу, которая по заданному числу N, находит самую красивую последовательность, состоящую из N чисел.

Входные данные
Во входном файле находится число N (1 ≤N ≤ 20).

Выходные данные
Выведите в выходной файл N чисел – элементы найденной последовательности, упорядоченные по неубыванию.

Примеры тестов :

входные данные
2

выходные данные
1
3

@Super-Hacker · 19.06.2020, 20:15

Ограничения до 20, значит можно перебрать каждое число

Добавлено через 3 минуты
То есть так

C++

while(не все числа в массиве размера N стали 9){
for(1...n)
{
     for(1...9)
}
findBeut() // пусть тут мы ищем М и сравнимаем с минимумом
}

Добавлено через 3 минуты
Но вроде ответ всегда

1, 2, ...n - 1, n + 1

@Bleach163 · 19.06.2020, 23:11

Super-Hacker, хорошо бы просто перебрать, но тут натуральные числа, а не цифры, то есть все целые от 1 до бесконечности.

Тем не менее, я попытался перебрать... И вижу последовательность из степеней тройки. Для краткости S - последовательность.
N = 1, M = 1, S = 1 (по логике)
N = 2, M = 4, S = 1, 3 (из примера)
N = 3, M = 13, S = 1, 3, 9 (перебрал числа от 1 до 200)
N = 4, M = 40, S = 1, 3, 9, 27 (перебрал числа от 1 до 100)

И всё довольно просто, жалко я не додумался до этого без перебора.
Есть последовательность, позволяющая получить все целые числа в промежутке [1;M].
Добавим в последовательность одно число x = M * 2 + 1.

Получим:
Промежуток [1; M], который уже был.
Промежуток [M+1; M*2] = [x-M; x-1].
Само число x = M*2+1.
Промежуток [M*2+2; M*3+1] = [x+1; x+M].

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

@TheCalligrapher · 20.06.2020, 06:44

Сообщение от kate_sam

алгебраической суммы

Что в данном случае имеется в виду? Судя по примеру, числа последовательности могут входить в сумму как со знаком +, так и со знаком -. Но понятие алгебраической суммы такого не подразумевает. Так откуда взялись отрицательные слагаемые?

Сообщение от kate_sam

Напишите программу, которая по заданному числу N, находит самую красивую последовательность, состоящую из N чисел.

Если числа последовательности могут входить в сумму как со знаком +, так и со знаком -, то в задаче сразу же проглядывает намек на симметричную троичную систему счисления

То есть навскидку в качестве решения я бы предложил последовательность степеней 3: 1, 3, 9, 27... и все.

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

@Slavo4ka · 02.05.2022, 21:27

Сообщение от Bleach163

Ну а почему степень тройки

Вы в этом уверенны?

@kate_sam 0 / 0 / 0 Регистрация: 25.11.2018 Сообщений: 15
		1
	Найти самую "красивую" последовательность, состоящую из N чисел 19.06.2020, 15:31. Показов 2481. Ответов 4 Метки нет (Все метки) Не могу решить эту задачу уже 3 дня, не понимаю в чем логика, может быть кто-то догадается и сможет мне объяснить ?) Задача №1850. Красивая последовательность Красотой последовательности состоящей из N натуральных чисел, будем называть минимальное натуральное число M, не представимое в виде алгебраической суммы некоторых элементов данной последовательности. Например, красота последовательности 2,3,4 равна 8 (1=−2+3, 2=−2+4, 3=3, 4=4, 5=2+3, 6=2+4, 7=4+3, 8=?). Напишите программу, которая по заданному числу N, находит самую красивую последовательность, состоящую из N чисел. Входные данные Во входном файле находится число N (1 ≤N ≤ 20). Выходные данные Выведите в выходной файл N чисел – элементы найденной последовательности, упорядоченные по неубыванию. Примеры тестов : входные данные 2 выходные данные 1 3 0

@Bleach163 440 / 283 / 183 Регистрация: 23.06.2018 Сообщений: 651
	19.06.2020, 23:11	3
	Сообщение было отмечено kate_sam как решение Решение Super-Hacker, хорошо бы просто перебрать, но тут натуральные числа, а не цифры, то есть все целые от 1 до бесконечности. Тем не менее, я попытался перебрать... И вижу последовательность из степеней тройки. Для краткости S - последовательность. N = 1, M = 1, S = 1 (по логике) N = 2, M = 4, S = 1, 3 (из примера) N = 3, M = 13, S = 1, 3, 9 (перебрал числа от 1 до 200) N = 4, M = 40, S = 1, 3, 9, 27 (перебрал числа от 1 до 100) И всё довольно просто, жалко я не додумался до этого без перебора. Есть последовательность, позволяющая получить все целые числа в промежутке [1;M]. Добавим в последовательность одно число x = M * 2 + 1. Получим: Промежуток [1; M], который уже был. Промежуток [M+1; M2] = [x-M; x-1]. Само число x = M2+1. Промежуток [M2+2; M3+1] = [x+1; x+M]. Ну а почему степень тройки - думаю вы и сами выразите, если понадобится. 1

@TheCalligrapher Вездепух 11691 / 6370 / 1723 Регистрация: 18.10.2014 Сообщений: 16,052
	20.06.2020, 06:44	4
	Сообщение от kate_sam алгебраической суммы Что в данном случае имеется в виду? Судя по примеру, числа последовательности могут входить в сумму как со знаком `+`, так и со знаком `-`. Но понятие алгебраической суммы такого не подразумевает. Так откуда взялись отрицательные слагаемые? Сообщение от kate_sam Напишите программу, которая по заданному числу N, находит самую красивую последовательность, состоящую из N чисел. Если числа последовательности могут входить в сумму как со знаком `+`, так и со знаком `-`, то в задаче сразу же проглядывает намек на симметричную троичную систему счисления То есть навскидку в качестве решения я бы предложил последовательность степеней 3: 1, 3, 9, 27... и все. Другими словами, перед вами классическая Задача о Гирях для равноплечных рычажных весов. Ее просто "замаскировали", чтобы труднее было искать готовый ответ в интернете. 1

@Slavo4ka 0 / 0 / 0 Регистрация: 15.08.2021 Сообщений: 1
	02.05.2022, 21:27	5
	Сообщение от Bleach163 Ну а почему степень тройки Вы в этом уверенны? 0

Опции темы

Найти самую "красивую" последовательность, состоящую из N чисел

Решение