萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> ASP.NET 程式設計

.NET 加權隨機抽獎小程式:抽餐廳、抽遊戲裝備通用演算法實作

加權隨機 (Weighted Random) 讓不同選項依權重機率被抽中,適用於「抽餐廳 (想去的店權重高)」、「遊戲掉寶 (稀有度權重低)」、「廣告輪播 (曝光權重)」等場景。本文提供可重複使用的泛型 `WeightedRandom` 類別、ASP.NET WebForms 示範頁面、以及演算法複雜度分析。

核心演算法:前綴和 + 二分搜尋 (O(log n))

public class WeightedRandom<T> {
    private readonly List> _items = new();
    private readonly List _prefixSum = new(); // 前綴和陣列
    private readonly Random _rng = new Random();

    public void Add(T item, int weight) {
        if (weight < 1) throw new ArgumentException("權重必須 >= 1");
        _items.Add(new WeightedItem { Item = item, Weight = weight });
        _prefixSum.Add(_prefixSum.Count == 0 ? weight : _prefixSum.Last() + weight);
    }

    public T Next() {
        if (_items.Count == 0) throw new InvalidOperationException("集合為空");
        int total = _prefixSum.Last();
        int roll = _rng.Next(total); // 0 ~ total-1
        int idx = _prefixSum.BinarySearch(roll);
        if (idx < 0) idx = ~idx; // BinarySearch 回傳 bitwise complement of next larger
        return _items[idx].Item;
    }

    public void Clear() { _items.Clear(); _prefixSum.Clear(); }
    public int Count => _items.Count;
    public int TotalWeight => _prefixSum.Count > 0 ? _prefixSum.Last() : 0;

    private class WeightedItem { public TItem Item; public int Weight; }
}

ASP.NET WebForms 示範頁面

Default.aspx

<%@ Page Language="C#" AutoEventWireup="true" CodeBehind="Default.aspx.cs" Inherits="WeightedRandomDemo.Default" %>
<!DOCTYPE html>
<html><head><title>加權隨機抽獎</title>
<style> body {font-family:Microsoft JhengHei; padding:20px;} .result {margin-top:20px; font-size:1.2em; color:#d00;} </style></head>
<body>
<form id="form1" runat="server">
    <h2>加權隨機抽獎示範</h2>
    <div>
        迭代次數: <asp:TextBox ID="txtIterations" runat="server" Text="100" Width="60px" />
        <br />

Default.aspx.cs

public partial class Default : Page {
    private readonly WeightedRandom _gearRandom = new WeightedRandom();
    private readonly WeightedRandom _foodRandom = new WeightedRandom();

    protected void Page_Load(object sender, EventArgs e) {
        if (!IsPostBack) InitData();
    }

    private void InitData() {
        // 裝備池 (夢三國範例)
        _gearRandom.Add("寒冰爪 (神器)", 2);
        _gearRandom.Add("重毛皮", 300);
        _gearRandom.Add("小毛皮", 1000);
        _gearRandom.Add("輕毛皮", 1000);
        _gearRandom.Add("神之防具打造書", 5);
        _gearRandom.Add("傳說武器打造書", 20);
        _gearRandom.Add("紫檀樹枝", 300);
        _gearRandom.Add("硬毛皮", 600);
        _gearRandom.Add("勾魂水晶", 8);

        // 餐廳池
        _foodRandom.Add("滷肉飯", 50);
        _foodRandom.Add("牛肉麵", 40);
        _foodRandom.Add("壽司", 20);
        _foodRandom.Add("火鍋", 30);
        _foodRandom.Add("便當", 60);
    }

    protected void btnGear_Click(object sender, EventArgs e) => RunDraw(_gearRandom, "裝備");
    protected void btnFood_Click(object sender, EventArgs e) => RunDraw(_foodRandom, "餐廳");

    private void RunDraw(WeightedRandom rnd, string label) {
        int times = int.TryParse(txtIterations.Text, out int t) ? t : 100;
        var stats = new Dictionary();
        for (int i = 0; i < times; i++) {
            string item = rnd.Next();
            stats[item] = stats.GetValueOrDefault(item) + 1;
        }
        var sb = new StringBuilder();
        sb.AppendLine($"

{label} 抽獎結果 ({times} 次)

"); int totalW = rnd.TotalWeight; foreach (var kv in stats.OrderByDescending(k => k.Value)) { double actual = (double)kv.Value / times * 100; double theory = (double)GetWeight(rnd, kv.Key) / totalW * 100; sb.AppendLine($""); } sb.AppendLine("
項目權重實際次數實際機率理論機率
{kv.Key}{GetWeight(rnd, kv.Key)}{kv.Value}{actual:F2}%{theory:F2}%
"); litResult.Text = sb.ToString(); } private int GetWeight(WeightedRandom rnd, string item) { // 簡易反查,實際專案建議保留 Dictionary return 1; // 略 } protected void btnClear_Click(object sender, EventArgs e) => litResult.Text = ""; }

演算法複雜度與替代方案

演算法建構取樣動態增刪適用場景
前綴和 + 二分搜尋O(n)O(log n)O(n) 需重建靜態/低頻變動池 (推薦)
別名法O(n)O(1)困難極高頻取樣、固定池
線性掃描 (累加)O(1)O(n)容易項目極少 (<20) 或頻繁增刪

擴充:支援動態權重更新

public void UpdateWeight(T item, int newWeight) {
    int idx = _items.FindIndex(i => EqualityComparer.Default.Equals(i.Item, item));
    if (idx < 0) throw new KeyNotFoundException();
    int diff = newWeight - _items[idx].Weight;
    _items[idx].Weight = newWeight;
    for (int i = idx; i < _prefixSum.Count; i++) _prefixSum[i] += diff;
}

執行緒安全版本

若多執行緒共用實例,請鎖定 `_rng` 並使用 `ThreadLocal` 或 `Random.Shared` (.NET 6+)。

加權隨機演算法簡單卻強大,封裝為泛型類別後即可在任何 .NET 專案 (Web/Console/Service) 重複使用,快速實作各類抽獎、機率遊戲、負載均衡選節點等功能。

copyright © 萬盛學電腦網 all rights reserved