15.10.2019, 05:45 [+3 UTC]
в нашей команде: 3 883 чел. | участники онлайн: 0 (рекорд: 21)

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

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

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.77 (31.05.2019)
JS-v.1.34 | CSS-v.3.35

Общие новости:
28.04.2019, 09:13

Форум:
11.10.2019, 14:47

Последний вопрос:
14.10.2019, 21:36
Всего: 150595

Последний ответ:
15.10.2019, 02:42
Всего: 259215

Последняя рассылка:
14.10.2019, 18:15

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

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

Наша кнопка:

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

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

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

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

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

zdwork
Статус: 6-й класс
Рейтинг: 736
Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 423
solowey
Статус: Бакалавр
Рейтинг: 336

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

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

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

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

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

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

Ответ # 278859 от zdwork (6-й класс)

Здравствуйте, 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 Лысков Игорь Витальевич (Старший модератор)

Консультировал: zdwork (6-й класс)
Дата отправки: 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.14944 сек.

© 2001-2019, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.77 от 31.05.2019
Версия JS: 1.34 | Версия CSS: 3.35