Помогите разобраться с алгоритмом: определить по мишени результаты соревнований по стрельбе

[Вероника99]

Надо написать программу на Си,но я что-то вообще не знаю даже с чего начать в этом задании((
Вот мое решение
Я насчитала 188 очков на мишени, а это число на 3 не делится ровно.
1 стрелок - 1+2+3+5+10+50
2 стрелок - 25+20+20+3+2+1
3 стрелок - 20+10+10+5+1+25
Один из стрелков попал в отметку "25" другого стрелка )

[Serge_Bliznykov]

Сообщение от Вероника99

Один из стрелков попал в отметку "25" другого стрелка )

Откуда Вы это знаете?! Я не увидел этого утверждения в условиях задачи.
может быть, в единицу дважды попали?!

А алгоритм, имхо, чисто переборный. у нас есть 8 выстрелов ниже средней линии (кроме 50). Нужно взять все варианты 5 из 8.
и проверить, можно ли из оставшихся чисел суммированием получить равное число очков.


p.s. а как Вы получили результат? Он очень похож на правильный!

[Smitt&Wesson]

Сфера фантастики. Кто Вам такие задачки задаёт? Наверное уроды, которые никогда на стрельбах не бывали. Или террористы, готовящие шахидок (уродство в высшей сфере своего проявлния!). Ни один, уважающий себя стрелок, не будет стрелять, в уже расстрелянную мишень. В общем, мир - свихнулся окончательно!

[rrrFer]

На прологе такие задачи решать удобно. Тем же подходом и на Си можно решить, но неудобно: http://pro-prof.com/archives/1299 (см. "задачи на установление соответствия" - тебе надо установить соответствие между стрелками и выстрелами). На плюсах еще, наверное, можно использовать тот же подход, что и в известной задаче о размене валюты.

[Smitt&Wesson]

17 выстрелов, на три не делится, хоть об стену головой. Кто-то смухлевал или выстрелил в воздух. Короче, задача решения не имеет.

[rrrFer]

check(L):- not(member(50, L)), !; maplist(p, L).
p(Val):- Val < 20; Val = 50.

pp(L1, L2, L3):-
	%L1 = [X1, _, _, _, _, _], member(X1, [1,2,3,5,10,20,25,50]), 
	L1 = [_, _, _, _, _, _],
	L2 = [_, _, _, _, _, _], L3 = [_, _, _, _, _, _], Sum = 71,!, 
	
	L1 = [25|LL1],
	permutation([50,20,20,3,2,25,1,5,20,10,10,10,3,5,1,2,1], Per1), 

	append(LL1, Per2, Per1), sumlist(L1, Sum),  
	append(L2, L3, Per2), sumlist(L2, Sum), sumlist(L3, Sum), 

	check(L1), check(L2), check(L3).

Но это решение наверное нет смысла переводить на плюсы
Если нельзя вывести что в 25 попали дважды - то сумма не 71, и программа будет работать дольше. Если список в permutation как-то переупорядочить неудачно - то программа доже может работать долго, вроде бы. Тут машина пролога перемешивает список и разделяет его на 3 части, но она не учитывает что если переставить местами элементы списка [10, 10] то получится тот же список (вобщем количество проверок можно сильно сократить, но надо думать). Тут тупое решение.

вообще не знаю даже с чего начать в этом задании((

начать надо с генерации перестановок. На самом деле, их не так много.
Тебе надо заполнить 2 списка (сгенерировать 12 элементов из заданного набора), третий набор получится сам.

Генерировать надо без перестановок - тогда получится менее 262 144 (это очень верхняя оценка) вариантов.
Если генерировать с перестановками (как делает permutation пролога) - получится меньше 11 019 960 576 вариантов (это тоже верхняя оценка).
Разница очевидна.

А в коде выше генерируются не 2, а все 3 списка, кроме того.

[Smitt&Wesson]

Приняли участие три стелка. Каждый зделал по шесть выстрелов. Один, попал в пулю другого (25).
3 * 6 = 21. На мишени 17-ть попаданий. Где ещё 21-17+1 = 3 попадания?
Какая рограмма? Задача не решена в условиях! Обалдели что-ли?

[Вероника99]

Сообщение от Smitt&Wesson

17 выстрелов, на три не делится, хоть об стену головой. Кто-то смухлевал или выстрелил в воздух. Короче, задача решения не имеет.

Да,я тоже на этом застряла, может быть все таки ошибка в условии

[BDA]

Smitt&Wesson, 3 * 6 = 18, так что найти нужно только 1 выстрел.
Он мог промахнуться или попасть в одно из попаданий:
не подходят: 188 (+0), 190 (+2), 191 (+3), 193 (+5), 208 (+20), 238 (+50)
подходят: 189 (+1), 198 (+10), 213 (+25)

[rrrFer]

Smitt&Wesson, 3 * 6 = 18, так что найти нужно только 1 выстрел.

хм, достал калькулятор, посчитал по твоей формуле, все сходится.