c ++明明的隨機數

Problem statement:

問題陳述：

Write an application code that will suggest movies from a list randomly and there won't be any repeat while suggesting the movies. That means the same movie won't be suggested twice though it will be done randomly. Input will be a movie list.

編寫應用程序代碼，以隨機建議列表中的電影，并且在建議電影時不會重復。 這意味著盡管會隨機播放同一部電影，但不會兩次被推薦。 輸入將是電影列表。

Prerequisite: Shuffling a given array in O(n) time using Fisher-Yates algorithm

先決條件： 使用Fisher-Yates算法在O(n)時間內對給定數組進行混洗

Example:

例：

Input:
["D-DAY", "RAINCOAT", "OCTOBER","LUNCHBOX", "BARFI", "RAAZI","PIKU"]
Movie suggestion list can be
"BARFI"
"PIKU"
"RAAZI"
"OCTOBER"
"D_DAY"
"LUNCHBOX"
"RAINCOAT"

Solution

解

We can use Fisher-Yates random shuffling algorithm to solve this problem. Firstly, we need to create a map to store indexes of the movies as we will shuffle based on their indexes.

我們可以使用Fisher-Yates隨機改組算法來解決此問題。 首先，我們需要創建一個地圖來存儲電影的索引，因為我們將根據電影的索引進行隨機播放。

So the map will be:

因此，地圖將為：

KEY	VALUE
1	"D-DAY"
2	"RAINCOAT"
3	"OCTOBER"
4	"LUNCHBOX"
5	"BARFI"
6	"RAAZI"
7	"PIKU"

So our movie list will be converted as: [1,2,3,4,5,6,7]

因此，我們的電影列表將被轉換為：[1,2,3,4,5,6,7]

Then we will shuffle using the Fisher-Yates algorithm

然后，我們將使用Fisher-Yates算法進行洗牌

At each step iteration, we will suggest movie[i]. Below is the detailed algorithm for suggesting movie randomly

在每一步迭代中，我們都會建議movie [i] 。 以下是隨機建議電影的詳細算法

The detailed algorithm will be,

詳細的算法將是

For i=n-1 to 1
Pick and element in the range [0,i-1] randomly
Swap the randomly picked element with a[i]
// since it's not going to be reshuffled again 
// as we are decrementing i , 
// thus it's guaranteed that it won't be suggested twice 
Recommend movie[a[i]]
Decrement i
End for loop

So, how this guarantees unique suggestion each time?

那么，如何保證每次的獨特建議呢？

Because, we are fixing the i^th element after the swap and decrementing i, so that the movie that got suggested never takes part again in swaps.

因為，我們在交換之后固定了^第 i ^個元素，并減小了i ，以便所建議的電影再也不會參與交換。

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
void recommend_movie_randomly(vector<string> movies)
{
srand(time(0));
map<int, string> mymap;
int n = movies.size();
for (int i = 0; i < n; i++) {
mymap[i] = movies[i];
}
vector<int> arr(n); //stores the indexes
for (int i = 0; i < n; i++)
arr[i] = i;
//shiffling randomly and suggesting movie 
//at each iteartion
for (int i = n - 1; i >= 1; i--) {
//j will be a random no with in range 0 to i-1
int j = rand() % i;
//swap ith index with jth
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
//suggest the ith movie now
cout << "Suggesting next movie...\n";
cout << mymap[arr[i]] << endl;
}
}
int main()
{
//input list
vector<string> movie_list{ "D-DAY", "RAINCOAT", "OCTOBER", "LUNCHBOX", "BARFI", "RAAZI", "PIKU" };
cout << "Recommending movies randomly from the list\n";
recommend_movie_randomly(movie_list);
return 0;
}

Output:

輸出：

Recommending movies randomly from the list
Suggesting next movie...
RAAZI
Suggesting next movie...
OCTOBER
Suggesting next movie...
PIKU
Suggesting next movie...
D-DAY
Suggesting next movie...
RAINCOAT
Suggesting next movie...
LUNCHBOX

---

---

Also tagged in: Synopsys

還標記在： Synopsys

翻譯自: https://www.includehelp.com/icp/suggesting-movie-randomly-from-a-list-cpp-program.aspx

c ++明明的隨機數