18.01.2020, 04:29 [+3 UTC]
в нашей команде: 4 150 чел. | участники онлайн: 3 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.80 (15.01.2020)
JS-v.1.35 | CSS-v.3.36

Общие новости:
06.01.2020, 22:45

Форум:
13.01.2020, 16:40

Последний вопрос:
18.01.2020, 02:32
Всего: 151434

Последний ответ:
17.01.2020, 19:30
Всего: 259652

Последняя рассылка:
18.01.2020, 00:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
01.01.2017, 01:21 »
svrvsvrv
Спасибо за такую хорошую и подробную консультацию. [вопрос № 190363, ответ № 274500]
11.09.2009, 13:05 »
Владимир Лазурко
Спасибо за отличную возможность написать дополнительное описание рассылки! Теперь в вопросах в моей рассылке будет меньше неясностей.
03.06.2010, 13:30 »
Наколай Игумнов
Спасибо огромное за решения! [вопрос № 178745, ответ № 261824]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 958
Gluck
Статус: Студент
Рейтинг: 504
Зенченко Константин Николаевич
Статус: Старший модератор
Рейтинг: 284

Перейти к консультации №:
 

Консультация онлайн # 196602
Раздел: • С / С++
Автор вопроса: moonfox (Посетитель)
Отправлена: 07.10.2019, 20:44
Поступило ответов: 2

Здравствуйте! Прошу помощи в следующем вопросе:

Напишите программу, перебирающую все перестановки массива букв в лексикографическом порядке. Программа должна работать не более чем за O(n!*n) шагов.

Заранее спасибо.

Состояние: Консультация закрыта

Ответ # 278859 от Gluck (Студент)

Здравствуйте, moonfox!

#include <algorithm>
#include <string>
#include <iostream>
 
int main()
{
    std::string s = "acb"; // что переставляем
    std::sort(s.begin(), s.end());
    do
    {
        std::cout << s << std::endl;
    } while(std::next_permutation(s.begin(), s.end()));
}

Последнее редактирование 08.10.2019, 11:27 Лысков Игорь Витальевич (Старший модератор)

Консультировал: Gluck (Студент)
Дата отправки: 07.10.2019, 21:54

5
нет комментария
-----
Дата оценки: 08.10.2019, 15:09

Рейтинг ответа:

+1

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Ответ # 278865 от solowey (Специалист)

Здравствуйте, moonfox!
Вот еще один вариант:

#include <iostream>
#include <set>
#include <string>
#include <cstring>

using namespace std;

int factorial(int i)
{
	if (i == 0) return 1;
	else return i*factorial(i - 1);
}

int main()
{
	char chars[] = "fdsgcba";

	// получаем размер массива
	int size = sizeof(chars) / sizeof(chars[0]) - 1; // -1 для отсечения \0 (окончания строки). иначе он будет учитыватся в переборе.
	
	char temp; // временная переменная для обмена элементов местами

	int count = 0; // счетчик перебора
	// Сортировка массива пузырьком
	for (int i = 0; i < size - 1; i++) {
		for (int j = 0; j < size - i - 1; j++) {
			if (chars[j] > chars[j + 1]) {
				// меняем элементы местами
				temp = chars[j];
				chars[j] = chars[j + 1];
				chars[j + 1] = temp;

				++count;
			}
		}
	}

	// Вывод отсортированного массива на экран
	for (int i = 0; i < size; i++) {
		cout << chars[i] << " ";
	}
	cout << endl;

	cout << "Count: " << count << endl;
	cout << "O(n!*n): " << factorial(size) * size << endl;

	return 0;
}

На выходе:
a b c d f g s
Count: 17
O(n!*n): 35280


Консультировал: solowey (Специалист)
Дата отправки: 08.10.2019, 15:47

Рейтинг ответа:

+1

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 196602

solowey
Специалист

ID: 400484

# 1

= общий = | 08.10.2019, 10:17 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
moonfox:

А что такое O(n!*n)?

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 2

= общий = | 08.10.2019, 11:38 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
solowey:

Это временная сложность алгоритма smile
Т.к. за сколько "шагов" должен быть получен результат, в зависимости от размерности аргумента.
Кстати, приведенная программа вроде как вкладывается в этот критерий.

-----
Последнее редактирование 08.10.2019, 11:39 Лысков Игорь Витальевич (Старший модератор)

=====
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен

solowey
Специалист

ID: 400484

# 3

= общий = | 08.10.2019, 12:13 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

т.е. число шагов для n = 3 число шагов будет 3! * 3 = 18. не больше 18 шагов. я правильно понял?

Лысков Игорь Витальевич
Старший модератор

ID: 7438

# 4

= общий = | 08.10.2019, 15:40 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер
solowey:

Правильно

=====
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.14647 сек.

© 2001-2020, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.80 от 15.01.2020
Версия JS: 1.35 | Версия CSS: 3.36