БлогNot. Расстановка M элементов в кольцо размерности N

Расстановка M элементов в кольцо размерности N

Требуется расставить M элементов, которые обозначены натуральными числами 1, 2,... ,M, в кольцо размерности N, начав с позиции номер K, номера позиций считаются с единицы.

Это не задача Иосифа Флавия, так как никто не выбывает. Но это и проще в решении, никакой массив не нужен, а функция lastPosition, определяющая позицию последнего из M поставленных в кольцо элементов, имеет вычислительную сложность O(1).

Вторая функция с названием printPositions печатает расстановку в консоль, в исходнике программки расстановка вот такая:

расстановка M элементов по кругу размерности N, начиная с элемента номер K
расстановка M элементов по кругу размерности N, начиная с элемента номер K

Реализация на C++ проверена в консоли QT 5.X.

#include <iostream>
using namespace std;

/* n Размерность кольца
   m Количество расставляемых элементов
   k Первая позиция для расстановки
   Не контролирует корректность данных
*/
int lastPosition (int n, int m, int k) {
    if (m <= n - k + 1) return m + k - 1;
    m = m - (n - k  + 1);
    return (m % n == 0)? n : (m % n);
}

int printPositions (int n, int m, int k) {
    if (n<1 || k<1 || k>n || m<1) return -1; //Проверка корректности данных
    cout << endl;
    for (int i=1; i<k; i++) cout << "0\t";
    int num = 1, pos = k;
    for (int i=1; i<=m; i++) {
       cout << num++ << "\t";
       if (pos++==n) { cout << endl; pos = 1; }
    }
    return 0;
}

int main() {
    int n = 6;
    int m = 10;
    int k = 3;
    cout << "Last position number = " << lastPosition(n, m, k);
    cout << endl << "Positions:";
    printPositions(n, m, k);
    cin.get(); return 0;
}

18.03.2018, 09:41 [1641 просмотр]


теги: c++ числа

К этой статье пока нет комментариев, Ваш будет первым