Незнакомцы в креслах

Нужно зарелизить решение следующей проблемы.
Есть N кресел и M пассажиров.
Требуется рассадить этих несчасных душененавистников,
чтобы расстояния между ними были максимальны из возможного.

Асм крутизна не нужна и даже противопоказана, так как задача решается один раз по вызову проги.

 

Например, 6 чел в 10 креслах можно рассадить как
1111100001
или
1010101011
или
1110101001

второй вариант наверное самый предпочтительный

 

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

 

Примерно так.

Код (Text):

1. #include <iostream>
2. #include <stdlib.h>
3. int main (int argc, char* argv[])
4. {
5.     if (argc<3)
6.     {
7.         std::cout<<"N M"<<std::endl;
8.         return 0;
9.     }
10.     int N = atoi(argv[1]);
11.     int M = atoi(argv[2]);
12.     if (N<=M)
13.     {
14.         std::cout<<"N<=M"<<std::endl;
15.         return 0;
16.     }
17.  
18.     if (M==0)
19.     {
20.         std::cout<<"M==0"<<std::endl;
21.         return 0;
22.     }
23.    
24.     int arr[N];
25.     for (int i=0; i<N; i++)
26.         arr[i] = 0;
27.     arr[0]=1;
28.     int N1 = N - 1;
29.     int M1 = M - 1;
30.     while (M1)
31.     {
32.         int N2 = N1/M1;
33.         int Rem = N1%M1;
34.         int M2 = M1 - Rem;
35.         for (int i=0; i<M2; i++)
36.             arr[(N - N1 -1 )+i*N2 + N2] = 1;
37.         N1 = N1 - M2*N2;
38.         M1 = M1 - M2;
39.     }
40.  
41.     for (int i=0; i<N; i++)
42.         std::cout<<arr[i]<<",";
43.     std::cout<<std::endl;
44. }

 

На счет быдлокодерства эт хорошо, еще не хватало тут минимаксов, линейного программирования и прочих брахистотронов!!!
Мда, мой прежний вариант с шагом (N-1) div (M-1) не очень..., идея повторять процесс циклически
для оставшихся мест это ценная мысль, спасибо. Буду пробовать.

 

persicum
Если в условии под "расстояния между ними" понимать наименьше из попарных расстояний, то (N-1) div (M-1) как раз и будет решением, разве нет?

 

green
Вроде простая проблема, а все мозги обломал уже =)))
Ща буду Сишный код пробовать...

Ну смотри, если взять шаг (N-1) div (M-1), то 5 из 10 рассядутся как
1010101010

но это ж не оптимальный вариант, так лучше будет
1010101001

 

persicum
попробуй for(i=0;i<M;i++) A[(i*(N-1)+(M-1)/2)/(M-1)]=1;

 

Black_mirror
крутта, очень крутта!!!
и программируется проще, и главное, результат качественнее и равномернее.
Кста, это видимо аналог Брезенхема, так можно ломанные рисовать, приближенные к прямым.

А точно эта формула ни при каких м и н не будет сажать двоих в одно кресло?

 

Радуюсь-ненарадуюсь на формулу Black_mirror =)))
Садим 6 на 14 креслах.
Через остатки имеем
10101001001001
по формуле имеем
10010100101001

 

persicum

(i/(M-1)) * (N-1) // перебирает от 0 до N-1 с шагом 1/(M-1)
+ 1/2 // округление вверх

те то о чем тут говорили, но красивее записано