Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.10.2018, 17:31   #1
Progway
 
Регистрация: 10.04.2016
Сообщений: 8
Вопрос Нумерация размещений без повторений

Доброго времени суток, очень нужна помощь, я новичок в c++, прощу помогите с задачей!

Условие: Построить комбинаторный объект с заданным номером и определить номер комбинаторного объекта при условии если комбинаторные объекты размещены из N элементов по K местам без повторений

Формула размещений без повторений: A = N!/(N-K)!
Progway вне форума Ответить с цитированием
Старый 14.10.2018, 15:25   #2
Progway
 
Регистрация: 10.04.2016
Сообщений: 8
По умолчанию

В программе надо по номеру рассчитать размещение комбинаторных объектов без повторений
Пример входных данных:
N = 3 ( размещаются три объекта: 0, 1, 2)
K = 2 (объекты размещаются по двум местам)
Таком результат размещения без повторений 3-х объектов по 2-м местам:
01
02
10
12
20
21
(код для построения размещений у меня есть)

Необходимо написать код для поиска такого размещения по порядковому номеру. Вот алгоритм для расчёта размещения по номеру на примере:
Пусть N= 4 (цифры от 0 до 3), K = 2 (места для размещения цифр), number = 5,
формала для расчёта размещений без повторений: A = N! / (N-K)!
01 02 03 10 12 13 20 21 23 30 31 32
Решение:
number / A = number // N-1! / ((N-1) - (K-1))! =
number % N-1! / ((N-1) - (K-1))! =
5 // 3! / (3-1)! = 1 5 % 3! / (3-1)! = 2 | на первое место из цифр 0 1 2 3 выбираем первое - 1 (отсчёт ведётся с нуля)
Дальше остаток от первого деления (число 2) делим
2 // 2! / (2-0)! = 2 2 % 2! / (2-0)! = 0 | на второе место из цифр 0 2 3 выбираем второе - 3 (отсчёт ведётся с нуля), остаток от деления = 0, значит расчёт прекращается
И того ответ: 13

У меня есть программа для расчёта номера перестановок, но переделать её для расчёта номера размещений не выходит
Код:
#include <iostream>
#include<string>
using namespace std;

int n, *m, number, d, s, *cc, ii;
char *a;
string c, per;

int fact(int n)
{
	if (n == 0)
	{
		return 1;
	}
	return n * fact(n - 1);
}

void search(int k)
{
	if (k == n)
	{
		for (int i = 0; i < n; i++) { cout << a[i]; }
	}
	else
	{
		int nn = n - (k + 1);
		int celoe;
		celoe = number / fact(nn);
		int schet;
		schet = 0;
		for (int j = 0; j < n; j++)
		{
			if (m[j] == 1)
			{
				if (schet == celoe)
				{
					a[k] = c[j];
					m[j] = 0;
					break;
				}
				else schet++;
			}
		}
		number = number % fact(nn);
		search(k + 1);
	}
}
void getNumber(int f)
{
	if (f == d)
	{
		cout << s;
	}
	else
	{
		int ii = 0;
		for (int i = 0; i < n; i++)
		{

			if (c[i] == per[f])
			{
				break;
			}
			else ii++;
		}
		int p = 0; //счетчик
		for (int j = 0; j < ii+1; j++)
		{
			if (m[j] == 1)
				p++;
		}
		m[p] = 0;
		int dd = d - (f + 1);
		s = s + (p - 1) * fact(dd);
		getNumber(f + 1);
	}
}

int main()
{
	cin >> c;
	n = c.length();
	a = new char[n];
	m = new int[n];
	for (int i = 0; i < n; i++)
	{
		m[i] = 1;
	}
	cin >> number;
	int k = 0;
	int s = 0;
	search(k);
	cin >> per; // вводим перестановку
	d = per.length(); // длина перестановки
	int f = 0;
	for (int i = 0; i < n; i++)
	{
		m[i] = 1;
	}
	getNumber(f);
	system("pause");
	return 0;
}

Последний раз редактировалось Progway; 14.10.2018 в 15:32.
Progway вне форума Ответить с цитированием
Старый 14.10.2018, 18:56   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

http://cppalgo.blogspot.com/2012/03/
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Последовательность чисел без повторений Вероника99 Помощь студентам 6 27.05.2015 17:11
Заполнить матрицу числами без повторений в строке OziFaker Visual C++ 0 26.11.2012 21:05
массивы в Бейсике без повторений Romka12345 Microsoft Office Word 5 01.12.2011 22:27
генерация сочетаний без повторений nowaalex Общие вопросы C/C++ 8 01.11.2010 00:29
Массив без повторений Uzenec Помощь студентам 2 17.01.2008 08:23