在Java核心技術一書(我用第八版）中有一個實例(P79)，用來完成：
產生一個抽彩游戲中的隨機數(shù)組合。
其中，實現(xiàn)防止重復抽中用的算法是:
// r是隨機數(shù)，不會超界；ｎ由numbers數(shù)組的length得道
numbers[r] = numbers[n - 1];
n--;
我沒看懂這個算法是怎么做到防止重復抽中的。請勞煩詳細解釋下，謝謝。
FYI:
代碼：
import java.util.*;
/**
* This program demonstrates array manipulation.
* @version 1.20 2004-02-10
* @author Cay Horstmann
*/
public class LotteryDrawing
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("How many numbers do you need to draw? ");
int k = in.nextInt();
System.out.print("What is the highest number you can draw? ");
int n = in.nextInt();
// fill an array with numbers 1 2 3 . . . n
int[] numbers = new int[n];
for (int i = 0; i < numbers.length; i++)
numbers[i] = i + 1;
// draw k numbers and put them into a second array
int[] result = new int[k];
for (int i = 0; i < result.length; i++)
{
// make a random index between 0 and n - 1
int r = (int) (Math.random() * n);
// pick the element at the random location
result[i] = numbers[r];
// move the last element into the random location
numbers[r] = numbers[n - 1];
n--;
}
// print the sorted array
Arrays.sort(result);
System.out.println("Bet the following combination. It'll make you rich!");
for (int r : result)
System.out.println(r);
}
}
1 回答
慕少森
TA貢獻2019條經驗 獲得超9個贊
這是一個數(shù)組內部取隨機值后換位置的算法,每次取數(shù)組中的隨機數(shù)后,把這個隨機數(shù)與數(shù)組尾部的值換位,這樣取過的值全部移動到數(shù)組尾部,而新的隨機值會在0和n-1之間,也就是從頭部到最后一個未換位的位置之間取,因此不會有重復值出現(xiàn).
比如:
numbers = [0,1,2,3,4,5],
假如r=2,則取出一個隨機值numbers[2] ,也就是數(shù)字2,
然后進行換位,numbers[r] = numbers[n - 1],2被換到數(shù)組最后一位,數(shù)組此時變成:
[0,1,5,3,4,2],
此時5換到了前面,這時n--后,再次取隨機值時是從[0,1,5,3,4,2]中取了(加粗部分),所以新的隨機值必定不會包含已經取出的2.
同理,再次取值時,這個值會放到倒數(shù)第二位.
添加回答
舉報
0/150
提交
取消