помогал ребенку делать математику.
такие задачки (своими словами):

1.
в школе все заразились шахматами и устроили шахматный турнир. в нем дают 3 очка за победу, 1 очко за ничью и 0 за проигрыш.
Маша похвасталась, что за 38 сыгранных партий она набрала 80 очков.
какое максимальное количество партий Маша проиграла?

2.
число 14 можно представить суммой 6ти нечетных чисел. порядок чисел при этом не играет роли.
сколько разных вариантов/комбинаций существует для этого?


И вот я думаю, что кроме как перебором это не решить.
Или решить?

Здравствуйте, paul.marx, Вы писали:

PM>в школе все заразились шахматами и устроили шахматный турнир. в нем дают 3 очка за победу, 1 очко за ничью и 0 за проигрыш.
PM>Маша похвасталась, что за 38 сыгранных партий она набрала 80 очков.
PM>какое максимальное количество партий Маша проиграла?

Тут просто же. Нужно минимизировать количество партий путем максимизации количества очков, которые нужно набрать.
Т.е. 80 очков за минимальное количество партий это 26 выигрышей и 2 ничьи. Остается максимум 10 проигрышей.

80/3 = 26 (берем только целую часть).
Оставшиеся 2 очка от 80 добираем 2-мя ничьими.
Оставшиеся партии это проигрыши.

Вторая задачка это уже комбинаторика вроде бы.

Здравствуйте, paul.marx, Вы писали:

PM>И вот я думаю, что кроме как перебором это не решить.
PM>Или решить?

Перебором довольно просто выходит.

9 1 1 1 1 1
7 3 1 1 1 1
5 5 1 1 1 1
5 3 3 1 1 1
3 3 3 3 1 1

Другими способами задействовать 6 чисел не получится

Здравствуйте, paul.marx, Вы писали:

PM>помогал ребенку делать математику.
PM>такие задачки (своими словами):

PM>1.
PM>в школе все заразились шахматами и устроили шахматный турнир. в нем дают 3 очка за победу, 1 очко за ничью и 0 за проигрыш.
PM>Маша похвасталась, что за 38 сыгранных партий она набрала 80 очков.
PM>какое максимальное количество партий Маша проиграла?

w*3 + d = 80
w + d + f = 38

w>=0, d>=0, f>=0; w, d, f целые
max f

чтобы максимизировать f, нужно минимизировать w+d
чтобы минимизировать w+d, нужно, чтобы из (w*3+d = 80) было максимально w
w = 26, d = 2 (80 div 3 * 3; 80 mod 3)

f = 10.

PM>2.
PM>число 14 можно представить суммой 6ти нечетных чисел. порядок чисел при этом не играет роли.
PM>сколько разных вариантов/комбинаций существует для этого?

(2a+1) + (2b+1) + (2c+1) + (2d+1) + (2e+1) + (2f+1) = 14
2a + 2b + 2c + 2d + 2e + 2f = 8
a+b+c+d+e+f = 4
дальше — перебор
1+1+1+1+0+0 => 3+3+3+3+1+1
2+1+1+0+0+0 => 5+3+3+1+1+1
2+2+0+0+0+0 => 5+5+1+1+1+1
3+1+0+0+0+0 => 7+3+1+1+1+1
4+0+0+0+0+0 => 9+1+1+1+1+1

PM>2.
PM>число 14 можно представить суммой 6ти нечетных чисел. порядок чисел при этом не играет роли.
PM>сколько разных вариантов/комбинаций существует для этого?

Пришла пора познакомить ребенка с динамическим программированием

Здравствуйте, sergey.p., Вы писали:

SP>Пришла пора познакомить ребенка с динамическим программированием

И с линейным тоже.
Первая задачка — это вообще классика симплекс-метода.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, sergey.p., Вы писали:

SP>>Пришла пора познакомить ребенка с динамическим программированием

К>И с линейным тоже.
К>Первая задачка — это вообще классика симплекс-метода.

Задача целочисленного программирования является в общем случае NP-полной.
Симплекс-метод, применяемый для решения задач линейного программирования имеет экспоненциальную сложность, хотя и эффективен на практике.
Существуют полиномиальные алгоритмы для решения задач линейного программирования.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, sergey.p., Вы писали:

SP>>Пришла пора познакомить ребенка с динамическим программированием

К>И с линейным тоже.
К>Первая задачка — это вообще классика симплекс-метода.

Если кто-то не понял, то первая задача не является задачей линейного программирования.
Иначе Маша бы проиграла 11.(3) партий.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, paul.marx, Вы писали:


PM>>2.
PM>>число 14 можно представить суммой 6ти нечетных чисел. порядок чисел при этом не играет роли.
PM>>сколько разных вариантов/комбинаций существует для этого?

К>(2a+1) + (2b+1) + (2c+1) + (2d+1) + (2e+1) + (2f+1) = 14
К>2a + 2b + 2c + 2d + 2e + 2f = 8
К>a+b+c+d+e+f = 4
К>дальше — перебор
К>1+1+1+1+0+0 => 3+3+3+3+1+1
К>2+1+1+0+0+0 => 5+3+3+1+1+1
К>2+2+0+0+0+0 => 5+5+1+1+1+1
К>3+1+0+0+0+0 => 7+3+1+1+1+1
К>4+0+0+0+0+0 => 9+1+1+1+1+1

Я не понял ход мыслей. Можно объяснить пожалуйста?

Здравствуйте, e.thrash, Вы писали:

ET>Я не понял ход мыслей. Можно объяснить пожалуйста?

Ну буквально же:
1) заменил "сумму нечётных" на взвешенную сумму любых чисел (заменил Odd на 2*Nat+1)
2) получил a+b+c+d = Const
3) поскольку Const маленькое, то руками сделал перебор: лексикографически возрастающая последовательность (просто чтобы не запутаться и ничего не упустить и не повторить) лексикографически убывающих наборов (поскольку наборы эквивалентны с точностью до перестановки)
4) восстановил нечётные числа