Выяснить является ли последовательность перестановкой числового ряда

@GreedWood · Регистрация: 21.02.2018

Author24 — интернет-сервис помощи студентам

Нужна помощь

Дано некоторое натуральное n (n ≤ 100) и целые числа а1 , а2, an

Выяснить есть ли последовательность – перестановкой чисел 1, 2......

Данная задача есть на форуме, но на Паскаль...

(Выяснить, является ли последовательность перестановкой чисел)

@Fixer_84 · 25.02.2018, 19:29

GreedWood, здравствуйте! Можно перебрать все комбинации с помощью встроенной функции:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
bool isPerm(int* x, int* y, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (x[i] != y[i])
            return false;
    }
    return true;
}
 
int main()
{
    int n;
    bool flag = false;
    cout << "Enter a quantoty of numbers:\n";
    cout << "n = ";
    cin >> n;
    int* arr = new int[n];
    int* perm = new int[n];
    cout << "Enter some numbers:\n";
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        perm[i] = i + 1;
    }
    do
    {
        if (isPerm(arr, perm, n))
        {
            cout << "Yes!\n";
            flag = true;
            break;
        }
    } while (next_permutation(perm, perm + n));
    if (!flag)
        cout << "No!\n";
    delete [] arr;
    delete [] perm;
    system("pause");
    return 0;
}

Можно, также, отсортировать один из массивов, а затем просто их сравнить (так, конечно, будет быстрее):

C++

#include <bits/stdc++.h>
 
using namespace std;
 
bool isPerm(int* x, int* y, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (x[i] != y[i])
            return false;
    }
    return true;
}
 
int main()
{
    int n;
    cout << "Enter a quantoty of numbers:\n";
    cout << "n = ";
    cin >> n;
    int* arr = new int[n];
    int* perm = new int[n];
    cout << "Enter some numbers:\n";
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        perm[i] = i + 1;
    }
    sort(arr, arr + n);
    if (isPerm(arr, perm, n))
        cout << "Yes!\n";
    else
        cout << "No!\n";
    delete [] arr;
    delete [] perm;
    system("pause");
    return 0;
}

Байт · 25.02.2018, 19:41

Если я правильно понял задание, то нужно
а) Чтобы все числа были 1 <= ai <= n
б) Чтобы не было повторов

Добавлено через 5 минут
Fixer_84, В вашем втором коде массив perm совершенно не нужен. Можно сравнивать с i+1

@Fixer_84 · 25.02.2018, 19:50

Сообщение от Байт

В вашем втором коде массив perm совершенно не нужен. Можно сравнивать с i+1

Байт, спасибо за ваше замечание. Опять поторопился. Конечно, так будет проще:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n;
    bool flag = true;
    cout << "Enter a quantoty of numbers:\n";
    cout << "n = ";
    cin >> n;
    int* arr = new int[n];
    cout << "Enter some numbers:\n";
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for (int i = 0; i < n; i++)
    {
        if (arr[i] != i + 1)
        {
            cout << "No!\n";
            flag = false;
            break;
        }
    }
    if (flag)
        cout << "Yes!\n";
    delete [] arr;
    system("pause");
    return 0;
}

@GreedWood · 26.02.2018, 17:43 **[ТС]**

спасибо)

@GreedWood 0 / 0 / 0 Регистрация: 21.02.2018 Сообщений: 8
		1
	Выяснить является ли последовательность перестановкой числового ряда 21.02.2018, 19:29. Показов 1156. Ответов 4 Метки нет (Все метки) Нужна помощь Дано некоторое натуральное n (n ≤ 100) и целые числа а1 , а2, an Выяснить есть ли последовательность – перестановкой чисел 1, 2...... Данная задача есть на форуме, но на Паскаль... (Выяснить, является ли последовательность перестановкой чисел) 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	25.02.2018, 19:41	3
	Если я правильно понял задание, то нужно а) Чтобы все числа были 1 <= ai <= n б) Чтобы не было повторов Добавлено через 5 минут Fixer_84, В вашем втором коде массив perm совершенно не нужен. Можно сравнивать с i+1 1

@GreedWood 0 / 0 / 0 Регистрация: 21.02.2018 Сообщений: 8
	26.02.2018, 17:43 [ТС]	5
	спасибо) 0

Опции темы