Народ, задачка для досуга...(и мне заодно поможете)
Есть таблица ASCII, есть массив char[256]...
Как рандомно (случ.образом) и быстро
заполнить все эелементы массива всеми
элементами таблицы.
Заранее спасибо!!!
Здравствуйте KAY, Вы писали:
KAY>Народ, задачка для досуга...(и мне заодно поможете) KAY>Есть таблица ASCII, есть массив char[256]... KAY>Как рандомно (случ.образом) и быстро KAY>заполнить все эелементы массива всеми KAY>элементами таблицы.
1. Копируем таблицу как есть (ну, в смысле, заполняем числами 0…255)
2. Берем 2 случайных числа i и j
3. Меняем элементы с номерами i и j местами
4. Повторяем это дело пока все элементы не будут изменены
Здравствуйте KAY, Вы писали:
KAY>Народ, задачка для досуга...(и мне заодно поможете) KAY>Есть таблица ASCII, есть массив char[256]... KAY>Как рандомно (случ.образом) и быстро KAY>заполнить все эелементы массива всеми KAY>элементами таблицы. KAY>Заранее спасибо!!!
#include "algorithm"
...
const int s = 256;
char a[s] = {...};
char r[s];
copy(a, a + s, r);
random_shuffle(r, r + s);
Здравствуйте Рек, Вы писали:
Рек>Здравствуйте KAY, Вы писали:
KAY>>Народ, задачка для досуга...(и мне заодно поможете) KAY>>Есть таблица ASCII, есть массив char[256]... KAY>>Как рандомно (случ.образом) и быстро KAY>>заполнить все эелементы массива всеми KAY>>элементами таблицы. KAY>>Заранее спасибо!!!
Рек>
Рек>#include "algorithm"
Рек>...
Рек>const int s = 256;
Рек>char a[s] = {...};
Рек>char r[s];
Рек>copy(a, a + s, r);
Рек>random_shuffle(r, r + s);
Рек>
Рек>Копируем, и хорошенько встряхиваем...
Усложним задание...
эту последовательность символов нужно будет повторить после
Здравствуйте KAY, Вы писали:
KAY>Усложним задание... KAY>эту последовательность символов нужно будет повторить после
Когда Вы случайно перемешиваете таблицу — Вы используете датчик псевдо-случайных чисел. Т.е. насколько я понимаю инициализируя его, к примеру, каждый раз от 5 (кажется ф-я srand()), Вы каждый раз будете получать одинаковые последовательности чисел. Запомните чем инициализировали датчик, и потом повторите инициализацию тем же числом....
Здравствуйте KAY, Вы писали:
KAY>Народ, задачка для досуга...(и мне заодно поможете) KAY>Есть таблица ASCII, есть массив char[256]... KAY>Как рандомно (случ.образом) и быстро KAY>заполнить все эелементы массива всеми KAY>элементами таблицы. KAY>Заранее спасибо!!!
Однажды ставилась подобная задача: требуется равномерн (с одинаковой вероятностью для каждого элемента) заполнить массив последовательностью элементов.
Решение: задача сводится к разработке алгоритма определения случайной позиции для очередного элемента; пользуясь генератором псевдо-случайных чисел получаем индекс для этого элемента, если элемент массива с этим индексом в массиве не занят (там 0), то записываем текущий элемент в массив по найденному индексу и повторяем описанные выше действия для следующего элемента последовательности, если же данный индекс "занят", то увеличиваем его (индекс) до тех пор, пока не найдём "свободный" элемент массива, если после очередного инкремента индекс выходит за пределы массива, то продолжаем поиск с начала массива. Когда найдём "пустой" элемент массива — пишем туда текущий элемент последовательности.
PS перед заполнением массив обнулить
PPS в данном случае тип данных элементов массива (char) и количество элементов исходной последовательности (256) ставят вопрос: как установить, что элемент массива не занят?
(т.к. не существует значения элемента массива, которое не присутствует в исходной последовательности). Ответ: заполнять массив последовательностью [1;255], тогда в массиве останется один элемент со значением 0.
Здравствуйте Chernishov Georgy, Вы писали:
CG>Здравствуйте KAY, Вы писали:
KAY>>Народ, задачка для досуга...(и мне заодно поможете) KAY>>Есть таблица ASCII, есть массив char[256]... KAY>>Как рандомно (случ.образом) и быстро KAY>>заполнить все эелементы массива всеми KAY>>элементами таблицы. KAY>>Заранее спасибо!!!
Я тут подумал зачем генерировать случайные числа если они итак уже есть.
Первой моей идей было выделить память без HeapAlloc, без HEAP_ZERO_MEMORY,
но уменя ничего не вышло
В итоге я наваял вот что (код ниже). Только с одним оговорм что массив это
будет использоваться только для чтения, то есть будет являться константным.
Если же надо писать в него то надо будет просто скопировать.
#include <windows.h>
#include <stdio.h>
void main()
{
char* p;
p = (char*)(void*)(0x400000+0x103F);
for (int i = 0; i < 255; i++)
printf("%d",p[i]);
};
Число 0x400000 это imagebase exeэшника
0x103F — точка входа (entry point)
то есть по адресу (0x400000+0x103F) по этому адресу начинается код а следовательно
мы имеем гарантию того что у нас будет равномерго распеделнная последовательность
псевдослучайных чисел.
Если каждый раз нужна новая последовательность то можно варьировать значение 0x103F
случайным образом. Здесь главное следить за тем чтобы ненатолкнуть на не доступные
участки памяти.
Да кстати это метод гарантирует, что мы сможем влюбое время полуть это последовательность
снова. Ну если конечно твой код не самомутирующийся.
Здравствуйте KAY, Вы писали:
KAY>Народ, задачка для досуга...(и мне заодно поможете) KAY>Есть таблица ASCII, есть массив char[256]... KAY>Как рандомно (случ.образом) и быстро KAY>заполнить все эелементы массива всеми KAY>элементами таблицы. KAY>Заранее спасибо!!! :shuffle:
Данная задача называется "Генерация случайных перестановок (random permutations)" и она не так проста как кажется с первого взгляда. Тут есть два основных подводных камня.
1. Пререстановки должны быть действительно случайные, т.е. все перестановки (при идеальном генераторе случайных чисел) должны быть равновероятны. Некоторые из привиденных здесь алгоритмов этому критерию явно не удовлетворяют.
К счастью есть достаточно простые алгоритмы (см. Кнута или поиском по интернету) генерации случайных престановок.
2. Гораздо более серьезный. Используя стандартные генераторы случайных чисел (ГСЧ) мы принципиально можем получить только некоторое подмножество перестановок. Так, если ГСЧ инициируется одним числом ивыдает 16-и битные числа, то мы можем получить не больше чем 2^16 перестановок, что значительно меньше чем 256!(! -это факториал).
Простой расчет показывает что разрядность (как минимум начального числа для ГСЧ) должна быть не меньше 1168 бит, а желательно и побольше. Но как написать такой ГСЧ и откуда брать начальное значение — это уже тема отдельного большого разговора.
Здравствуйте MichaelP, Вы писали:
MP>2. Гораздо более серьезный. Используя стандартные генераторы случайных чисел (ГСЧ) мы принципиально можем получить только некоторое подмножество перестановок. Так, если ГСЧ инициируется одним числом ивыдает 16-и битные числа, то мы можем получить не больше чем 2^16 перестановок, что значительно меньше чем 256!(! -это факториал). MP>Простой расчет показывает что разрядность (как минимум начального числа для ГСЧ) должна быть не меньше 1168 бит, а желательно и побольше. Но как написать такой ГСЧ и откуда брать начальное значение — это уже тема отдельного большого разговора.
На мой взгляд это вообще не проблемма. Ведь никто не говорит, что генератор нужно использовать 1 раз. Пожалуйста вызывай генератор случайных чисел [0..255] 256 раз.
Здравствуйте User99, Вы писали:
MP>>2. Гораздо более серьезный. Используя стандартные генераторы случайных чисел (ГСЧ) мы принципиально можем получить только некоторое подмножество перестановок. Так, если ГСЧ инициируется одним числом ивыдает 16-и битные числа, то мы можем получить не больше чем 2^16 перестановок, что значительно меньше чем 256!(! -это факториал). MP>>Простой расчет показывает что разрядность (как минимум начального числа для ГСЧ) должна быть не меньше 1168 бит, а желательно и побольше. Но как написать такой ГСЧ и откуда брать начальное значение — это уже тема отдельного большого разговора.
U>На мой взгляд это вообще не проблемма. Ведь никто не говорит, что генератор нужно использовать 1 раз. Пожалуйста вызывай генератор случайных чисел [0..255] 256 раз.
Это не поможет, различных вариантов будет все равно 2^16.
Рассмотрим ГС 2^2, который генерирует, например, следующую последовательность:
00, 01, 11, 10
Сколько раз его не вызывай, будет всего 4 различных варианта:
