0 / 0 / 0
Регистрация: 16.08.2019
Сообщений: 2
1

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

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

Author24 — интернет-сервис помощи студентам
Добрый день!
Необходимо поместить случайный символ алфавита в каждый элемент массива 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)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
16.08.2019, 13:23
Ответы с готовыми решениями:

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

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

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

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

13
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
16.08.2019, 13:30 2
Цитата Сообщение от Radogost01 Посмотреть сообщение
Необходимо поместить случайный символ алфавита в каждый элемент массива char[26], причем:
Здесь, наверное, проще всего запольнить массив буквами ABCDE......XYZ, потом перемешать их - std::random_shuffle, потом пробежаться по массиву и буквы, которые остались на прежнем месте поменять местами со следующим элементом.
2
601 / 438 / 137
Регистрация: 22.11.2017
Сообщений: 1,386
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
2489 / 1147 / 707
Регистрация: 25.04.2016
Сообщений: 3,294
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
27709 / 17327 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
16.08.2019, 19:16 5
Лучший ответ Сообщение было отмечено Radogost01 как решение

Решение

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

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

Добавлено через 1 минуту
Да и реализация алгоритма Фишера–Йетса одним постом выше (строки 10-13).
0
845 / 648 / 323
Регистрация: 24.02.2017
Сообщений: 2,289
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
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
16.08.2019, 20:18 8
Цитата Сообщение от Байт Посмотреть сообщение
Этот прием может привести к новым коллизиям. И что делать? Опять "пробежаться"? Не исключено попадание в бесконечный цикл.
К каким коллизиям? Если ты поменяешь местами букву А и букву Б, то ни одна из них не останется на своём месте. Если после перетасовки у тебя буква Ж осталась на месте, и ты её поменял местами со следующей буквой Ы, то тоже будет всё нормально
0
Комп_Оратор)
Эксперт по математике/физике
9005 / 4704 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 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
27709 / 17327 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
17.08.2019, 09:57 10
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
тоже будет всё нормально
да, верно.Ваша правдочка
А соображения равно-вероятностности, видимо, не так уж и важны...
1
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
17.08.2019, 10:18 11
Цитата Сообщение от Байт Посмотреть сообщение
А соображения равно-вероятностности, видимо, не так уж и важны...
Т.е. хочешь сказать, что если в случайной последовательности поменять местами два элемента она перестанет быть случайной?
Или какие там ещё соображения?
0
Комп_Оратор)
Эксперт по математике/физике
9005 / 4704 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
17.08.2019, 11:10 12
Цитата Сообщение от Байт Посмотреть сообщение
А соображения равно-вероятностности, видимо, не так уж и важны...
Те что остались на своих местах, можно менять с любыми, а не только между собой. Важно чтобы хотя бы половина не осталась на своих местах, как я понимаю.
Ну то есть, если то что стоит на своём месте поменять с чем угодно, то сразу два элемента окажутся на чужих местах. Энтропия растёт нелинейно) Ломать, - не строить.
Но перемешивание, конечно не самый красивый приём (имхо). Например, можно шуфлить до тех пор пока последовательность не отсортируется. Если шуфл честен, то когда-нибудь это произойдёт. Но такая сортировка ужасна конечно. А способ случайного размещения - вполне жизнеспособен.
1
Диссидент
Эксперт C
27709 / 17327 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
17.08.2019, 17:51 13
Цитата Сообщение от IGPIGP Посмотреть сообщение
Те что остались на своих местах, можно менять с любыми,
Да, конечно. Самый простой способ получить один из беспорядков - циклически сдвинуть. Но он, увы! - детерминирован.
Цитата Сообщение от IGPIGP Посмотреть сообщение
если то что стоит на своём месте поменять с чем угодно, то сразу два элемента окажутся на чужих местах.
И это верно.
Цитата Сообщение от IGPIGP Посмотреть сообщение
Но перемешивание, конечно не самый красивый приём (имхо)
Тут дело в том, что шуфл (самый честный) не дает равновероятностых последовательностей. Это уже обсуждалось в разделе Математика.
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
хочешь сказать, что если в случайной последовательности поменять местами два элемента она перестанет быть случайной? Или какие там ещё соображения?
Нет, не хочу. Хочу сказать другое. При таком действии вероятность появления разных "нужных" последовательностей может (и скорее всего - будет) отличаться.

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

Добавлено через 5 минут
Цитата Сообщение от Байт Посмотреть сообщение
не дает равновероятностых последовательностей
это смотря с каким начальным состоянием сравнивать (как наиболее вероятным). Шуфл достаточно честно перемешивает. И вопрос лишь в том сколько раз перемешать. Это похоже на размешивание пломбира с клубничным вареньем. Извините за банальность. Но иногда банальные вещи удивительно вкусны. Фраза принадлежит одному известному людоеду (не помню кому, именно).
0
17.08.2019, 18:11
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
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
Ответ Создать тему
Опции темы

Новые блоги и статьи
Использование связки C# и PHP в корпоративной разработке и микросервисной архитектуре
InfoMaster 16.01.2025
Введение в интеграцию C# и PHP В современной корпоративной разработке все чаще возникает потребность в создании гибких и масштабируемых решений, способных эффективно решать широкий спектр. . .
Как использовать Kerio дома для управления сетью и пользователями
InfoMaster 16.01.2025
Использование технологий для улучшения повседневной жизни стало неотъемлемой частью современного быта. Одной из таких технологий является Kerio — мощный инструмент для управления сетью и. . .
Есть ли будущее у DVD и Blu-ray?
InfoMaster 16.01.2025
В эпоху стремительного развития цифровых технологий и повсеместного распространения потоковых сервисов вопрос о будущем физических носителей информации становится все более актуальным. Особенно остро. . .
Как проводить научные вычисления на Python
InfoMaster 15.01.2025
Python стал одним из наиболее востребованных языков программирования в области научных вычислений благодаря своей простоте, гибкости и обширной экосистеме специализированных библиотек. Научные. . .
Создание игры типа Minecraft на PyGame/Python: пошаговое руководство
InfoMaster 15.01.2025
В данном руководстве мы рассмотрим процесс создания игры в стиле Minecraft с использованием библиотеки PyGame на языке программирования Python. Этот проект идеально подходит как для начинающих. . .
Как создать свою первую игру в стиле Doom на Unreal Engine
InfoMaster 15.01.2025
Разработка шутера от первого лица в стиле классического Doom представляет собой увлекательное путешествие в мир игрового программирования, где сочетаются творческий подход и технические навыки. . . .
Параллельное программировани­е: основные технологии и принципы
InfoMaster 15.01.2025
Введение в параллельное программирование Параллельное программирование представляет собой фундаментальный подход к разработке программного обеспечения, который позволяет одновременно выполнять. . .
Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD
InfoMaster 15.01.2025
В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .
Что такое CQRS и как это реализовать на C# с MediatR
InfoMaster 15.01.2025
Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .
Как настроить CI/CD с Azure DevOps
InfoMaster 15.01.2025
CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .
Как настроить CI/CD с помощью Jenkins
InfoMaster 15.01.2025
Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .
Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD
InfoMaster 14.01.2025
Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru