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

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

Модератор: Admin

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

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

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

Задача решена в Maple,но,может,в Mathcad всё можно решить проще?
Задача.Есть весы с чашками и даны грузы 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;

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

VFO
Сообщения: 4227
Зарегистрирован: Ср фев 27, 2002 8:03 pm

Сообщение VFO » Пн июн 20, 2005 3:12 pm

В детской энциклопедии (том по математике - это я помню, с него я начал знакомится с теорией чисел) задача о гирях решается через рассмотрение исчисления с разной базой. В Mathcad встроены двоичная, восьмеричная, десятеричная (умолчание) и шестнадцатеричные системы.
Другие системы можно запрограммировать. См.
http://twt.mpei.ac.ru/MAS/Worksheets/base2base.mcd
1000=1111101000b. Это значит 8+32+64+128+258+512=1000
Или я решаю другую задачу?
Перебор применяют, когда других идей нет...
Последний раз редактировалось VFO Пн июн 20, 2005 3:47 pm, всего редактировалось 1 раз.

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

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

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

YuK
Сообщения: 698
Зарегистрирован: Вт дек 09, 2003 7:42 pm

Сообщение YuK » Ср июн 22, 2005 5:42 am

То Ventura - если считать до 1000 в десятичной системе - то это будет ровно столько же, сколько в двоичной системе считать до 1111101000. VFO прекрасно все объяснил.
А что касается технологии необходимого вам перебора с меньшим кол-вом циклов - то для того чтобы Вам разобраться - заведите массив двоичных чисел и добавляйте по 1 к последнему разряду внутри одного единственного цикла.
YuK

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

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

Уважаемый YuK !
Не могли бы вы, пожалуйста, показать ход решения более подробно.
Так как с Mathcad я особо не работал и не знаком даже с самыми
простыми его структурами.
Спасибо.

YuK
Сообщения: 698
Зарегистрирован: Вт дек 09, 2003 7:42 pm

Сообщение YuK » Чт июн 23, 2005 6:23 am

Организуете цикл по N от 1 до 1000 - внутри цикла вызываете процедуру base2base (записываете число N в двоичном виде) - единичка на k-том месте означает присутствие в разложении элемента 2^k, 0 - его отсутствие. Тем самым сам набор для каждого N будет найдет - можете записать в массив эти двоичные числа и дальше с ними работать.
Процедуру можете взять здесь http://collab.mathsoft.com/read?70587,63e#70587.
Вопрос единственности такого представления отдельная задача - подумайте как с ней быть.
YuK

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

Сообщение ventura » Чт июн 23, 2005 10:59 am

Большое спасибо за помощь !