Как получить равное количество элементов после деления диапазона, оставляя остаток - PullRequest
Новая
       7

Как получить равное количество элементов после деления диапазона, оставляя остаток

1 голос
/ 24 марта 2019

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

MIN: 0 и MAX: 10, поэтому диапазон будет 10.

Я хочу разделить диапазон на n полей (пользователь дает этот ввод, поэтому он является переменным), а затем создать n потоков-детей, используя fork (), где каждый получит свой собственный поддиапазон этих чисел и выполнитнекоторый код, использующий эти числа, фактически он собирается проверить, является ли это число простым числом.
Так что моя проблема в том, что я не могу придумать формулу для записи, чтобы числа были разделены поровну.

Я пытался: 

    for(int i = 0; i<n; i++){
        //fork()
        int temp = MIN + (i*(RANGE/n));
        for(int a =; a< temp +(RANGE/n)+1; a++){
            //check if prime
            //other actions
         }
     }

Но я знаю, что это не будет работать правильно, потому что если у нас есть 3 потока (n), он будет проверять диапазоны (0,3), (3,6), (6,9), поскольку

(RANGE / n) дает 3

Это означает, что последнее число,в этом примере 10 никогда не будет проверяться в тех случаях, когда деление RANGE на число детей N оставляет остаток.
Есть ли какой-нибудь разумный способ разделить диапазон и проверить все числа по разному количеству процессов?каждый раз ?
заранее спасибо

Ответы [ 2 ]

0 голосов
/ 24 марта 2019

Как получить равное количество элементов после деления диапазона, оставляя остаток

Различные подходы.

Ключевой вопрос заключается в том, включены ли 0 и 10 в целочисленный диапазон: это [0... 10] или [0... 10) или ...? Обратите внимание на ] или )? Предположим, что конечные точки списков включены, а [0... 10] - это 11 различных целочисленных значений.

Примечание. Существуют такие крайности, как 11 чисел, разделенных на 12 групп.

Ниже представлен поддиапазон из первой 1/n части диапазона, затем 1/(n-1) части оставшегося диапазона и т. Д. 

void range(int n, int inclusive_min, int inclusive_max) {
  printf("Range [%d %d] / %d\n", inclusive_min, inclusive_max, n);
  for(int i = n; i > 0 && inclusive_min <= inclusive_max; i--) {
    int range = 1 + inclusive_max - inclusive_min;
    int sub_range = range/i;
    if (sub_range == 0) sub_range = 1;
    printf("Sub range [%d %d]\n", inclusive_min, inclusive_min + sub_range - 1);
    inclusive_min += sub_range;
  }
}

int main(void) {
  range(3, 0, 10);
  range(2, 0, 10);
  range(5, 0, 10);
  range(3, 0, 1);
  return 0;
}

выход 

Range [0 10] / 3
Sub range [0 2]
Sub range [3 6]
Sub range [7 10]
Range [0 10] / 2
Sub range [0 4]
Sub range [5 10]
Range [0 10] / 5
Sub range [0 1]
Sub range [2 3]
Sub range [4 5]
Sub range [6 7]
Sub range [8 10]
Range [0 1] / 3
Sub range [0 0]
Sub range [1 1]

Более элегантное решение, похожее на Алгоритм линии Брезенхема 

void range(int n, int inclusive_min, int inclusive_max) {
  printf("Range [%d %d] / %d\n", inclusive_min, inclusive_max, n);
  int range = 1 + inclusive_max - inclusive_min;
  int sub_range = range / n;
  int sub_range_res = range % n;
  int p = 0;
  for (int i = 0; i < n; i++) {
    int next = inclusive_min + sub_range;
    p += sub_range_res;
    if (2 * p >= n) {  // like p >= n/2 without integer truncation.
      p -= n;
      next++;
    }
    if (next > inclusive_min) {
      printf("Sub range %d:[%d %d]\n", i, inclusive_min, next - 1);
    }
    inclusive_min = next;
  }
}

выход 

Range [0 10] / 3
Sub range 0:[0 3]
Sub range 1:[4 6]
Sub range 2:[7 10]
Range [0 10] / 2
Sub range 0:[0 5]
Sub range 1:[6 10]
Range [0 10] / 5
Sub range 0:[0 1]
Sub range 1:[2 3]
Sub range 2:[4 6]
Sub range 3:[7 8]
Sub range 4:[9 10]
Range [0 1] / 3
Sub range 0:[0 0]
Sub range 2:[1 1]
0 голосов
/ 24 марта 2019

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

Вы можете использоватьполитика, начатая MAX.Затем создайте следующий интервал: {MAX-1, MAX-2}, например (и т. Д.), Пока у вас не будет количества требуемых диапазонов.

...