Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 0
Регистрация: 16.08.2019
Сообщений: 2
1

Случайным образом сгенерировать массив символов алфавита

16.08.2019, 13:23. Показов 1941. Ответов 13
Метки нет (Все метки)

Добрый день!
Необходимо поместить случайный символ алфавита в каждый элемент массива char[26], причем:
  • Нельзя заменить элемент самим собой, т. е. первой не может быть буква A;
  • Нельзя использовать одну и ту же букву несколько раз, т. е. если выбрана буква S, она больше не может встретиться в массиве.
Подозреваю, что использую кривой подход, помогите, пожалуиста, разобраться с логикой алгоритма:
На каждом шаге алгоритма создаю возможный пул символов pool размером [range].
Убираю из пула запрещенный порядковый элемент (A на первом шаге, B на втором и т. д.) и сдвигаю элементы влево.
Функцией rand() генерирую символ, затем также исключаю его из пула, элементы сдвигаются влево.
Исключенный порядковый элемент возвращается в пул, элементы сдвигаются вправо.
Итерация повторяется, пока в пуле не останется единственное возможное значение.
Вот мой код (для простоты тестирую пока на 10 буквах):
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// crypt_rand_test.cpp -- двигаем массив
#include <iostream>
#include <cstdlib>
#include <ctime>
const char order_letters[10] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};      // константный массив букв для сравнения
int main()                                                                                             //  с порядковым эл-том
{
    using namespace std;
    const int NUM_LETTERS = 10;
    char pool[NUM_LETTERS] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
    char CRYPT[NUM_LETTERS];
    for (int range = NUM_LETTERS; range > 0; range--)
    {
        cout << endl << "STEP " << (NUM_LETTERS - range);
        for (int order = 0; order < range - 1; order ++)
        {
            if (pool[order] == order_letters[NUM_LETTERS - range])
            {
                for (int i = NUM_LETTERS - range; i < range - 1; i++)               // сдвиг влево на эл-т, убираем из пула
                {                                                                                          // запрещ. порядковый эл-т
                    char temp = pool[i];
                    pool[i] = pool[i+1];
                    pool[i+1] = temp;
                }
                break;
            }
        }
        cout << endl << "allowed pool: " << endl;
        for (int j = 0; j < range - 1; j++)
            cout << pool[j] << "\t";
        srand(time(0));                                    // генерация случ. эл-та
        int index_rand = rand() % (range - 1);
        CRYPT[NUM_LETTERS - range] = pool[index_rand];
        cout << endl << "random from pool: " << pool[index_rand]
        << " [ " << index_rand << " ] "<< endl;
 
        for (int j = range - 1; j > NUM_LETTERS - range; j--)           // сдвиг вправо на эл-т, возвращ. на место 
        {                                                                                     // запрещ. порядк. эл-т
            char temp = pool[j-1];
            pool[j-1] = pool[j];
            pool[j] = temp;
        }
        if (index_rand > 0)
            index_rand += 1;                                                 // (index + 1 т. к. до этого сдвигали и нарушили нумерацию)
        for (int rand = 0; rand < range - 1; rand++)
        {
            if (pool[rand] == pool[index_rand])
            {
                for (index_rand; index_rand < range; index_rand ++)    // удаляем запрещенный выбранный эл-т
                {                                                                                // сдвиг влево  
                    char temp = pool[index_rand];
                    pool[index_rand] = pool[index_rand + 1];
                    pool[index_rand + 1] = temp;
                }
                break;
            }
        }
        cout << endl << "pool except random: " << endl;
        for (int j = 0; j < range - 1; j++)
            cout << pool[j] << "\t";
    }
    cout << endl << "Our CRYPT massiv: " << CRYPT << endl;
    return 0;
}

Заранее спасибо за ответ.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.08.2019, 13:23
Ответы с готовыми решениями:

Случайным образом сгенерировать массив из 20 чисел (в заданном диапазоне)
Создать программу на С++, в которой случайным образом генерируется массив из 20 чисел (в диапазоне...

Структуры. Создать массив из 10 точек, сгенерировать случайным образом координаты и массы
люди, у меня осталось одно задание: Структурный тип содержит поля: координаты х,у и массу...

Создать матрицу А(nxn), сгенерировать елементы случайным образом
Создать матрицу А(nxn), сгенерировать елементы случайным образом. Вычеслить индексы елементов...

Нужно сгенерировать элементы массива случайным образом с помощью функции rand
Нужно сгенерировать элементы случайным образом с помощью функции rand. Определить индексы...

13
6738 / 4537 / 1839
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
16.08.2019, 13:30 2
Цитата Сообщение от Radogost01 Посмотреть сообщение
Необходимо поместить случайный символ алфавита в каждый элемент массива char[26], причем:
Здесь, наверное, проще всего запольнить массив буквами ABCDE......XYZ, потом перемешать их - std::random_shuffle, потом пробежаться по массиву и буквы, которые остались на прежнем месте поменять местами со следующим элементом.
2
567 / 406 / 132
Регистрация: 22.11.2017
Сообщений: 1,053
16.08.2019, 15:58 3
Radogost01, привет!

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream> 
#include <random>
#include <algorithm>
#include <numeric>
 
int main()
{
    std::random_device rd;
    auto pyramid = [](bool cmp_value, bool acc) { return acc || cmp_value; };
    auto cmp = [](char c1, char c2) { return c1 == c2; };
 
    std::string line(26u, 'A'), line_shuffle(26u, 'A');
    std::iota(std::begin(line), std::end(line), 'A');
    std::copy(std::begin(line), std::end(line), std::begin(line_shuffle));
    for (;;)
    {
        std::shuffle(std::begin(line_shuffle), std::end(line_shuffle), rd);
        if (!std::inner_product(std::begin(line), std::end(line), std::begin(line_shuffle), false, pyramid, cmp))
            break;
    }
    std::cout << line_shuffle << "\n";
 
    system("pause");
    return 0;
}
1
Миниатюры
Случайным образом сгенерировать массив символов алфавита  
1507 / 905 / 584
Регистрация: 25.04.2016
Сообщений: 2,524
16.08.2019, 19:07 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define N 26
 
int main (void) {
    srand((unsigned int)time(NULL)/2);
    char a[N];
    for (int i=0; i<N; i++)         // заполняем по порядку
        a[i] = 'a' + i;
    for (int i=N-1; i>0; i--)       // перемешиваем случайным образом
        swap(a[i], a[rand() %i]);
    for (int i=0; i<N-1; i++)       // чтобы символы не оставались на своих местах
        if (a[i] == 'a'+i)
            swap(a[i], a[i+1]);
    for (int i=0; i<N; i++)         // выводим на экран
        cout << a[i];
    cout << endl;
    return 0;
}
Добавлено через 17 минут
или, например, так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define N 26
 
int main (void) {
    srand((unsigned int)time(NULL)/2);
    char a[N];
    for (int i=0; i<N; i++)         // заполняем по порядку
        a[i] = 'a' + i;
    for (int i=N-1; i>0; i--)       // перемешиваем случайным образом
        swap(a[i], a[rand() %i]);
    for (int i=0; i<N-1; i++)       // чтобы символы не оставались на своих местах
        if (a[i] == 'a'+i)
            swap(a[i], a[i++ +1]);
    for (int i=0; i<N; i++)         // выводим на экран
        cout << a[i] << ' ';
    cout << endl;
    return 0;
}
1
Эксперт C
26066 / 16256 / 3494
Регистрация: 24.12.2010
Сообщений: 35,626
16.08.2019, 19:16 5
Лучший ответ Сообщение было отмечено Radogost01 как решение

Решение

Цитата Сообщение от oleg-m1973 Посмотреть сообщение
потом перемешать их - std::random_shuffle
Дело в том, что это не дает равновероятностного распределения всех перестановок.
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
потом пробежаться по массиву и буквы, которые остались на прежнем месте поменять местами со следующим элементом.
Этот прием может привести к новым коллизиям. И что делать? Опять "пробежаться"? Не исключено попадание в бесконечный цикл.
Radogost01, в принципе ваш подход - правильный. И напоминает совершенно гениальный простой алгоритм со сложным названием, который неоднократно здесь обсуждался (поищу - дам ссылочку)
Одна беда. Вам нужны перестановки, именуемые "беспорядками", то есть такие, когда ни один элемент не остается на своем месте. И при вашем подходе вы можете в конце туннеля уткнуться в букву 'Z'
Задача ваша интересная, и над ней имеет смысл поразмыслить.
Если, конечно, не следовать правилу "Не получилась? - давай еще разок!" В программировании это правило порочно и приводит к непредсказуемости.
Кстати, для количества "беспорядков" есть хорошая длинная, но точная, формула.

Добавлено через 6 минут
Называется алгоритм "Тасование Фишера–Йетса в варианте Дуршенфельда"
А вот и реализация
Случайная перестановка элементов массива
Radogost01, но опять же, вашу задачу это не решает. Ибо вам нужны не просто перестановки, а перестановки беспорядочные
1
1507 / 905 / 584
Регистрация: 25.04.2016
Сообщений: 2,524
16.08.2019, 19:18 6
Цитата Сообщение от Байт Посмотреть сообщение
Этот прием может привести к новым коллизиям.
Если менять с соседним, то новые коллизии исключены.

Добавлено через 1 минуту
Да и реализация алгоритма Фишера–Йетса одним постом выше (строки 10-13).
0
607 / 458 / 269
Регистрация: 24.02.2017
Сообщений: 1,656
16.08.2019, 19:59 7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <ctime>
using namespace std;
 
int main()
{
  int m[26]={0},j=0;
  char simvol[26];
  srand(time(0));
 
  while(1){
    int a= rand() %26+1;
    int  flag=0;
    for(int i=0;i<26;i++){
      if(m[i]==a)flag=1;
      if(j==a-1)flag=1;
      }
    if(flag==0)m[j++]=a;
    if(j==26)break;
    }
  for(int i=0;i<26;i++)
      simvol[i]=m[i]+64;
  for(int i=0;i<26;i++)
     cout<<simvol[i]<<" ";
  cout<<"\n";
  for(char i='A';i<='Z';i++)
         cout<<i<<" ";
  system("pause");
  return 0;
}
0
6738 / 4537 / 1839
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
16.08.2019, 20:18 8
Цитата Сообщение от Байт Посмотреть сообщение
Этот прием может привести к новым коллизиям. И что делать? Опять "пробежаться"? Не исключено попадание в бесконечный цикл.
К каким коллизиям? Если ты поменяешь местами букву А и букву Б, то ни одна из них не останется на своём месте. Если после перетасовки у тебя буква Ж осталась на месте, и ты её поменял местами со следующей буквой Ы, то тоже будет всё нормально
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,270
Записей в блоге: 16
17.08.2019, 00:15 9
Ещё 5 коп.
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<set>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
 
class AlphaBetGenerator
{
public: 
    AlphaBetGenerator(char z, char a)
        :n(z-a+1 > 1 ? z-a+1 : 2)       
        ,newSeq(n)
        ,first(a)
    {       
        for (int i = 0; i < n; ++i) usedPositions.insert(i);
        generate();
    }
 
    void prnSeq()
    {
        for (const auto& a : newSeq)cout << char(first + a) << ' ';
    }
 
    const vector<int>& Seq() const{
        return newSeq
            ;
    }
 
private:
    void generate()
    {       
        int pos;
        set<int>::iterator itbeg, itend;
        for(int i = 0; i < n; ++i)
        {           
            while ((pos = rand() % usedPositions.size()) == i);
 
            itbeg = usedPositions.begin(), itend = usedPositions.end();
            for (int j=0; itbeg != itend; ++itbeg)
            {
                
                if (j == pos)
                {
                    newSeq.push_back(*itbeg);
                    
                    usedPositions.erase(itbeg);
                }
                    ++j;
            }           
        }       
    }
 
    set<int>usedPositions;
    vector<int>newSeq;
    int n;
    char first;
};
 
int main()
{
    srand((unsigned)time(0));
    AlphaBetGenerator Agr('Z','A'); 
    Agr.prnSeq();
    cout << endl;
    AlphaBetGenerator agr('z', 'a');
    agr.prnSeq();
    const vector<int> v = agr.Seq();
    cout << endl;
    for (auto a : v)cout << char(a+'a') <<' ';
    return 0;
}
0
Эксперт C
26066 / 16256 / 3494
Регистрация: 24.12.2010
Сообщений: 35,626
17.08.2019, 09:57 10
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
тоже будет всё нормально
да, верно.Ваша правдочка
А соображения равно-вероятностности, видимо, не так уж и важны...
1
6738 / 4537 / 1839
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
17.08.2019, 10:18 11
Цитата Сообщение от Байт Посмотреть сообщение
А соображения равно-вероятностности, видимо, не так уж и важны...
Т.е. хочешь сказать, что если в случайной последовательности поменять местами два элемента она перестанет быть случайной?
Или какие там ещё соображения?
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,270
Записей в блоге: 16
17.08.2019, 11:10 12
Цитата Сообщение от Байт Посмотреть сообщение
А соображения равно-вероятностности, видимо, не так уж и важны...
Те что остались на своих местах, можно менять с любыми, а не только между собой. Важно чтобы хотя бы половина не осталась на своих местах, как я понимаю.
Ну то есть, если то что стоит на своём месте поменять с чем угодно, то сразу два элемента окажутся на чужих местах. Энтропия растёт нелинейно) Ломать, - не строить.
Но перемешивание, конечно не самый красивый приём (имхо). Например, можно шуфлить до тех пор пока последовательность не отсортируется. Если шуфл честен, то когда-нибудь это произойдёт. Но такая сортировка ужасна конечно. А способ случайного размещения - вполне жизнеспособен.
1
Эксперт C
26066 / 16256 / 3494
Регистрация: 24.12.2010
Сообщений: 35,626
17.08.2019, 17:51 13
Цитата Сообщение от IGPIGP Посмотреть сообщение
Те что остались на своих местах, можно менять с любыми,
Да, конечно. Самый простой способ получить один из беспорядков - циклически сдвинуть. Но он, увы! - детерминирован.
Цитата Сообщение от IGPIGP Посмотреть сообщение
если то что стоит на своём месте поменять с чем угодно, то сразу два элемента окажутся на чужих местах.
И это верно.
Цитата Сообщение от IGPIGP Посмотреть сообщение
Но перемешивание, конечно не самый красивый приём (имхо)
Тут дело в том, что шуфл (самый честный) не дает равновероятностых последовательностей. Это уже обсуждалось в разделе Математика.
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
хочешь сказать, что если в случайной последовательности поменять местами два элемента она перестанет быть случайной? Или какие там ещё соображения?
Нет, не хочу. Хочу сказать другое. При таком действии вероятность появления разных "нужных" последовательностей может (и скорее всего - будет) отличаться.

Добавлено через 22 минуты
oleg-m1973, Понимаешь, математики такие зануды, что им мало просто случайности. Им подавай закон распределения этой случайности. И больше всего они любят равновероятностное, однородное распределение, типа "орел-решка". Тут к их услугам давно разработанный и мощный аппарат - Бернулли, Гаусс...
Вот для генерации просто перестановок алгоритм Фишера–Йетса именно и дает такое однородное распределение (в отличии от шуфла).
Но, вполне возможно, для данной задачи однородность не имеет решающего значения. И занудство математиков тут ни к чему. Не детерминировано? На каждом месте может оказаться любой элемент? - Уже хорошо!
Просто мне показалось любопытной возможность генерации этих "беспорядков" с равномерным распределением. И это - задача. Простого решения которой я не вижу.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,270
Записей в блоге: 16
17.08.2019, 18:11 14
Цитата Сообщение от Байт Посмотреть сообщение
Понимаешь, математики такие зануды
Это мягко сказано. Но в современном С++ очень много движков. Беда в том, что у символа алфавита нет значения сравнимого повесу (трудно сказать что я имел ввиду). Скорее всего это значение (код символа) характеризуется только уникальностью и номером следования в конкретном алфавите, навродь ASCII. Таким образом, любое размещение должно быть случайным, кроме конкретно выделенного и названного "неслучайным". Говоря о символах алфавита мы имеем ввиду (здесь) английский алфавит.

Добавлено через 5 минут
Цитата Сообщение от Байт Посмотреть сообщение
не дает равновероятностых последовательностей
это смотря с каким начальным состоянием сравнивать (как наиболее вероятным). Шуфл достаточно честно перемешивает. И вопрос лишь в том сколько раз перемешать. Это похоже на размешивание пломбира с клубничным вареньем. Извините за банальность. Но иногда банальные вещи удивительно вкусны. Фраза принадлежит одному известному людоеду (не помню кому, именно).
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.08.2019, 18:11

Сгенерировать случайным образом многочлен P(x) степени N и найти интеграл P(x) от a до b для заданных a и b
Сгенерировать случайным образом многочлен P(x) степени N и найти интеграл P(x) от a до b для...

Переставить строку из рандомных 16 символов 256 раз случайным образом
Здравствуйте. Помогите пожалуйста! Нужна программа для рандомного переставления букв в различных 16...

Массив: Заполнить массив из 10 элементов случайным образом в интервале (0..3).
Заполнить массив из 10 элементов случайным образом в интервале (0..3). Например:...

Заполнить массив случайным образом
Добрый день!!! Ребята, объясните пожалуйста, как выполнить такую задачу!!! По возможности,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.