Где много циклов

Форум пользователей пакета Mathematica

Модератор: Admin

ventura
Сообщения: 22
Зарегистрирован: Пн янв 24, 2005 7:08 pm

Где много циклов

Сообщение ventura » Пн июн 20, 2005 2:45 pm

Задача решена в Maple,но,может,в Mathematica всё можно решить проще?
Задача.Есть весы с чашками и даны грузы 1,2,4,8,16...
Необходимо проверить возможность составления любого веса от 1 до 1000,
причем единственным образом.Грузы ставятся на одну чашу весов.
Получается достаточно громоздкая запись с 11 циклами.Вопрос:можно ли
задачу решить,используя меньше циклов.Может каким-то образом
использовать масссив,процедуру.Подскажите,пожалуйста
(Обязательность введения 10 параметров проверено отдельно)
s:=0:
for p from 1 to N do
for a1 in [0,1] do
for a2 in [0,2] do
for a3 in [0,4] do
for a4 in [0,8] do
for a5 in [0,16] do
for a6 in [0,32] do
for a7 in [0,64] do
for a8 in [0,128] do
for a9 in [0,256] do
for a10 in [0,512] do
if a1+a2+a3+a4+a5+a6+a7+a8+a9+a10=p then s:=s+1
fi od od od od od od od od od od;
if s<>p then r:=r+1
fi;od;
if s=N and r=0 then print (N,"любой целый вес от 1 до указанного числа можно составить единственным способом")
fi;

Проверить - это просто перебрать. А грузики - степени двойки и каждого по одному.

malina
Сообщения: 24
Зарегистрирован: Пт фев 04, 2005 1:08 pm

Сообщение malina » Вт июн 21, 2005 3:46 pm

>Необходимо проверить возможность составления любого веса от 1 до 1000,
>причем единственным образом.

Поясните, пожалуйста, подробнее. Ведь чуть ниже вы пишете, что

>А грузики - степени двойки и каждого по одному.

Если грузиков по одному экземпляру каждого веса, то в любом случае разложение будет единственным. Поправьте меня, если ошибаюсь.

А в "Математике" такую задачу (если есть только по одному экземпляру грузиков) можно решить достаточно просто и быстро пользуясь тем, что веса грузов - степени двойки.
Например, если нужно узнать разложение веса в 25 Н, записываем
IntegerDigits[25, 2]
и получаем
{1, 1, 0, 0, 1}
Читаем нолики и единички справа налево и делаем вывод, что 25=1*2^0+0*2^1+0*2^2+1*2^3+1*2^4=1+8+16.
То есть для составления веса в 25 Н необходимо взять грузики с весом 1, 8 и 16.

ventura
Сообщения: 22
Зарегистрирован: Пн янв 24, 2005 7:08 pm

Сообщение ventura » Вт июн 21, 2005 7:28 pm

Уважаемый(ая) malina !
Вы совершенно правы,говоря,что если грузиков по одному экземпляру каждого веса,то в любом случае разложение будет единственным.Это просто, очевидно и понятно каждому.
Но задача заключается в том,чтобы это нам показал сам компьютер. То есть он должен перебором или каким-то другим способом выявить,что 25 можно составить только сложив грузы 1,8,16, а 26 соответственно 2,8,16.И так для КАЖДОГО груза
от 1 до 1000.
При помощи какой системы счисления будет решена задача-не важно.
Важно,чтобы все вычисления выполнялись автоматически(для двоичной системы-это возведение в степень,сложение и т.д.) и запись была короче,чем в исходном варианте.
В итоге мы должны получить только, что действительно
любой целый вес от 1 до указанного числа можно составить единственным способом.

malina
Сообщения: 24
Зарегистрирован: Пт фев 04, 2005 1:08 pm

Сообщение malina » Ср июн 22, 2005 4:50 pm

Ну ладно. Я понял задачу так: показать разложение определенного веса на заданные веса, являющиеся степенями двойки.

+++++ Код +++++

ot = 10; do = 18;
len = IntegerDigits[do, 2] // Length;
base = Table[2^i, {i, len - 1, 0, -1}];
For[ves = ot, ves <= do, ves++,
Print[ves, " = ", base*IntegerDigits[ves, 2, len]];
]
Clear[ot, do, len, base, ves];

+++++ Коду конец +++++
ot и do это соответственно левый и правый концы интервала разложения (для Вашей задачи нужно задавать ot=1; do=1000;).

Получается вот такое вот:

10 = {0, 8, 0, 2, 0}
11 = {0, 8, 0, 2, 1}
12 = {0, 8, 4, 0, 0}
13 = {0, 8, 4, 0, 1}
14 = {0, 8, 4, 2, 0}
15 = {0, 8, 4, 2, 1}
16 = {16, 0, 0, 0, 0}
17 = {16, 0, 0, 0, 1}
18 = {16, 0, 0, 2, 0}

Пример интерпретации: "Для того, чтобы составить груз весом в 18 у.е. нужно взять грузики в 16 у.е и 2 у.е".
Надеюсь, лишние нули Вас не смущают.
Последний раз редактировалось malina Ср июн 22, 2005 4:52 pm, всего редактировалось 1 раз.

ventura
Сообщения: 22
Зарегистрирован: Пн янв 24, 2005 7:08 pm

Сообщение ventura » Ср июн 22, 2005 7:14 pm

malina большое человеческое СПАСИБО !