2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение24.06.2012, 02:18 


25/03/10
590

(Оффтоп)

Почему мало элегантного? Если это полный код, то видно же что нет лишнего вроде var, begin, end и прочего синтаксиса.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение24.06.2012, 06:45 
Заслуженный участник
Аватара пользователя


13/08/08
14495
Насчёт количества вариантов. Их 16 (я там поправил), просто при копировании в сообщение упустил одну строку.
На самом деле это ActionScript для Flash, но все конструкции, особенно чисто вычислительные, там стандартны. А идею я же изложил. Кратный цикл, прямой подсчёт суммы и сравнение её с результатом.
При этом, конечно, просчитывается огромное количество заведомо непроходных вариантов, но для небольших значений это несущественно.
Циклы имеет смысл оптимизировать, если счёт идёт на триллионы, да и то...
Хотя вот я сейчас запустил разложение 10000 на те же слагаемые и там считалось несколько секунд. Ведь количество проверяемых вариантов увеличилось в 1000 раз. А если взять 100000, то комп задумается надолго. Но как раз в Паскале дело будет идти гораздо быстрее. Скрипт есть скрипт.

О параметрах цикла. Вот немного приукрашенный код:
Код:
N=1000;
m1=30; m2=81; m3=125;

n1=Math.floor(N/m1)+1; n2=Math.floor(N/m2)+1;n3=Math.floor(N/m3)+1;
K=0;

for (k1=0; k1<n1; k1++) {
   for (k2=0; k2<n2; k2++) {
      for (k3=0; k3<n3; k3++) {
          NK=k1*m1+k2*m2+k3*m3;
          if (Math.abs(NK-N)<2) {K=K+1;trace (NK+"="+k1+"*"+m1+"+"+k2+"*"+m2+"+"+k3+"*"+m3)}
}}}

trace ("Всего "+K+" вариантов")

1000=0*30+0*81+8*125
999=9*30+9*81+0*125
999=10*30+4*81+3*125
1001=13*30+6*81+1*125
1001=14*30+1*81+4*125
1000=25*30+0*81+2*125
Всего 6 вариантов


На Паскале цикл будет записываться так:

Код:
for k1:=1 to n1 do begin
     for k2:=1 to n2 do begin
          for k3:=1 to n3 do begin
                ....
          end;
      end;
end;


При желании можно вычислять параметры внутренних циклов непосредственно перед их началом, но для разовых расчётов на оптимизацию уйдёт гораздо больше времени, чем на сами расчёты :-) .

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение24.06.2012, 18:26 


25/03/10
590
Здорово! Спасибо большое!!! Сейчас пытаюсь разобраться и переписать!

-- Вс июн 24, 2012 19:22:53 --

А как у Вас используется K ? Оно не лишнее ли?

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение24.06.2012, 19:48 


25/03/10
590
А, понял, чтобы количество вариантов посчитать.

-- Вс июн 24, 2012 20:11:59 --

gris в сообщении #588182 писал(а):
[off]Я думал, Вы всерьёз про амфорную. Это название действительно было в Древней Греции. Вино и масло разливали в амфоры и надо было для определённого объёма жидкости подобрать набор амфор, в которые она бы вместилась. По существу, это и есть Ваша задача. Диофант Александрийский и начал свои исследования с амфорных задач.

Не подскажете, где можно об этом почитать. Гугл молчит.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение25.06.2012, 08:24 


28/11/11
2884
Стало интересно как задача решается не перебором.

-- 25.06.2012, 08:33 --

Общий вид линейного диофантова уравнения:
$$a_1 x_1+a_2 x_2 + \ldots + a_k x_k  =d$$
Где $d \text{ и } a_1,\, a_2,\, \ldots,\, a_k$ берутся из условия.

Как его решить в общем виде?

-- 25.06.2012, 08:40 --

Да, в "Конкретной математике" решение задачи про размен монет с помощью производящих функций $-$ отличный хинт.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение25.06.2012, 14:32 


25/03/10
590
gris, а как сделать цикл в цикле, чтобы количество типов задавалось пользователем? Чтобы N, m1, m2, m3 запрашивались и задавались я сделал.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение25.06.2012, 14:43 


28/11/11
2884
Однако метод производящих функций даст только точное равенство, а не приближенное. Не знаю, можно ли это обойти.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group