演算法(第四版)C#題解——1.5

来源:http://www.cnblogs.com/ikesnowy/archive/2017/10/07/7634797.html
-Advertisement-
Play Games

寫在前面整個項目都托管在了 Github 上:https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp這一節內容可能會用到的庫文件有 Measurement 和 TestCase,同樣在 Github 上可以找到。善用 Ctrl + F... ...


寫在前面

整個項目都托管在了 Github 上:https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp

這一節內容可能會用到的庫文件有 Measurement 和 TestCase,同樣在 Github 上可以找到。

善用 Ctrl + F 查找題目。

習題&題解

1.5.1

題目

使用 quick-find 演算法處理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。
對於輸入的每一對整數,給出 id[] 數組的內容和訪問數組的次數。

解答

quick-find 的官方實現:QuickFindUF.java

只要實現相應並查集,然後輸入內容即可。

增加一個記錄訪問數組次數的類成員變數,在每次訪問數組的語句執行後自增即可。

樣例輸出:

0 1 2 3 4 5 6 7 8 0 數組訪問:13
0 1 2 4 4 5 6 7 8 0 數組訪問:13
0 1 2 4 4 8 6 7 8 0 數組訪問:13
0 1 2 4 4 8 6 2 8 0 數組訪問:13
0 1 1 4 4 8 6 1 8 0 數組訪問:14
0 1 1 4 4 1 6 1 1 0 數組訪問:14
4 1 1 4 4 1 6 1 1 4 數組訪問:14
1 1 1 1 1 1 6 1 1 1 數組訪問:16
代碼

QuickFindUF.cs,這個類繼承了 UF.cs,重新實現了 Union() 和 Find() 等方法。

關於 UF.cs 可以參見原書中文版 P138 或英文版 P221 的演算法 1.5。

namespace UnionFind
{
    /// <summary>
    /// 用 QuickFind 演算法實現的並查集。
    /// </summary>
    public class QuickFindUF : UF
    {
        public int ArrayVisitCount { get; private set; } //記錄數組訪問的次數。

        /// <summary>
        /// 新建一個使用 quick-find 實現的並查集。
        /// </summary>
        /// <param name="n">並查集的大小。</param>
        public QuickFindUF(int n) : base(n) { }

        /// <summary>
        /// 重置數組訪問計數。
        /// </summary>
        public void ResetArrayCount()
        {
            this.ArrayVisitCount = 0;
        }
        
        /// <summary>
        /// 尋找 p 所在的連通分量。
        /// </summary>
        /// <param name="p">需要尋找的結點。</param>
        /// <returns>返回 p 所在的連通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            this.ArrayVisitCount++;
            return this.parent[p];
        }

        /// <summary>
        /// 判斷兩個結點是否屬於同一個連通分量。
        /// </summary>
        /// <param name="p">需要判斷的結點。</param>
        /// <param name="q">需要判斷的另一個結點。</param>
        /// <returns>如果屬於同一個連通分量則返回 true,否則返回 false。</returns>
        public override bool IsConnected(int p, int q)
        {
            Validate(p);
            Validate(q);
            this.ArrayVisitCount += 2;
            return this.parent[p] == this.parent[q];
        }

        /// <summary>
        /// 將兩個結點所在的連通分量合併。
        /// </summary>
        /// <param name="p">需要合併的結點。</param>
        /// <param name="q">需要合併的另一個結點。</param>
        public override void Union(int p, int q)
        {
            Validate(p);
            Validate(q);
            int pID = this.parent[p];
            int qID = this.parent[q];
            this.ArrayVisitCount += 2;

            // 如果兩個結點同屬於一個連通分量,那麼什麼也不做。
            if (pID == qID)
            {
                return;
            }

            for (int i = 0; i < this.parent.Length; ++i)
            {
                if (this.parent[i] == pID)
                {
                    this.parent[i] = qID;
                    this.ArrayVisitCount++;
                }
            }

            this.ArrayVisitCount += this.parent.Length;
            this.count--;
            return;
        }

        /// <summary>
        /// 獲得 parent 數組。
        /// </summary>
        /// <returns>id 數組。</returns>
        public int[] GetParent()
        {
            return this.parent;
        }
    }
}


Main 方法:

using System;
using UnionFind;

namespace _1._5._1
{
    /*
     * 1.5.1
     * 
     * 使用 quick-find 演算法處理序列 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 。
     * 對於輸入的每一對整數,給出 id[] 數組的內容和訪問數組的次數。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var quickFind = new QuickFindUF(10);

            foreach (string s in input)
            {
                quickFind.ResetArrayCount();

                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                int[] id = quickFind.GetParent();
                quickFind.Union(p, q);
                foreach (int root in id)
                {
                    Console.Write(root + " ");
                }
                Console.WriteLine("數組訪問:" + quickFind.ArrayVisitCount);
            }
        }
    }
}

 

1.5.2

題目

使用 quick-union 演算法(請見 1.5.2.3 節代碼框)完成練習 1.5.1。
另外,在處理完輸入的每對整數之後畫出 id[] 數組表示的森林。

解答

quick-union 的官方實現:QuickUnionUF.java

和上題一樣的方式,增加一個記錄訪問數組次數的類成員變數,在每次訪問數組的語句執行後自增即可。

程式輸出的森林,用縮進表示子樹:

|---- 0
    |---- 9
|---- 1
|---- 2
|---- 3
|---- 4
|---- 5
|---- 6
|---- 7
|---- 8
數組訪問:1
|---- 0
    |---- 9
|---- 1
|---- 2
|---- 4
    |---- 3
|---- 5
|---- 6
|---- 7
|---- 8
數組訪問:1
|---- 0
    |---- 9
|---- 1
|---- 2
|---- 4
    |---- 3
|---- 6
|---- 7
|---- 8
    |---- 5
數組訪問:1
|---- 0
    |---- 9
|---- 1
|---- 2
    |---- 7
|---- 4
    |---- 3
|---- 6
|---- 8
    |---- 5
數組訪問:1
|---- 0
    |---- 9
|---- 1
    |---- 2
        |---- 7
|---- 4
    |---- 3
|---- 6
|---- 8
    |---- 5
數組訪問:1
|---- 0
    |---- 9
|---- 1
    |---- 2
        |---- 7
    |---- 8
        |---- 5
|---- 4
    |---- 3
|---- 6
數組訪問:7
|---- 1
    |---- 2
        |---- 7
    |---- 8
        |---- 5
|---- 4
    |---- 0
        |---- 9
    |---- 3
|---- 6
數組訪問:3
|---- 1
    |---- 2
        |---- 7
    |---- 4
        |---- 0
            |---- 9
        |---- 3
    |---- 8
        |---- 5
|---- 6
數組訪問:3
代碼

QuickUnionUF.cs,這個類繼承了 UF.cs,重新實現了 Union() 和 Find() 等方法。

關於 UF.cs 可以參見原書中文版 P138 或英文版 P221 的演算法 1.5。

namespace UnionFind
{
    /// <summary>
    /// 用 QuickUnion 演算法實現的並查集。
    /// </summary>
    public class QuickUnionUF : UF
    {
        public int ArrayVisitCount { get; private set; } //記錄數組訪問的次數。

        /// <summary>
        /// 建立使用 QuickUnion 的並查集。
        /// </summary>
        /// <param name="n">並查集的大小。</param>
        public QuickUnionUF(int n) : base(n) { }

        /// <summary>
        /// 重置數組訪問計數。
        /// </summary>
        public virtual void ResetArrayCount()
        {
            this.ArrayVisitCount = 0;
        }

        /// <summary>
        /// 獲得 parent 數組。
        /// </summary>
        /// <returns>返回 parent 數組。</returns>
        public int[] GetParent()
        {
            return this.parent;
        }

        /// <summary>
        /// 尋找一個結點所在的連通分量。
        /// </summary>
        /// <param name="p">需要尋找的結點。</param>
        /// <returns>該結點所屬的連通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            while (p != this.parent[p])
            {
                p = this.parent[p];
                this.ArrayVisitCount += 2;
            }
            return p;
        }

        /// <summary>
        /// 將兩個結點所屬的連通分量合併。
        /// </summary>
        /// <param name="p">需要合併的結點。</param>
        /// <param name="q">需要合併的另一個結點。</param>
        public override void Union(int p, int q)
        {
            int rootP = Find(p);
            int rootQ = Find(q);
            if (rootP == rootQ)
            {
                return;
            }

            this.parent[rootP] = rootQ;
            this.ArrayVisitCount++;
            this.count--;
        }
    }

}


Main 方法

using System;
using UnionFind;

namespace _1._5._2
{
    /*
     * 1.5.2
     * 
     * 使用 quick-union 演算法(請見 1.5.2.3 節代碼框)完成練習 1.5.1。
     * 另外,在處理完輸入的每對整數之後畫出 id[] 數組表示的森林。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var quickUnion = new QuickUnionUF(10);

            foreach (string s in input)
            {
                quickUnion.ResetArrayCount();
                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                quickUnion.Union(p, q);
                int[] parent = quickUnion.GetParent();
                for (int i = 0; i < parent.Length; ++i)
                {
                    if (parent[i] == i)
                    {
                        Console.WriteLine("|---- " + i);
                        DFS(parent, i, 1);
                    }
                }
                Console.WriteLine("數組訪問:" + quickUnion.ArrayVisitCount);
            }
        }

        static void DFS(int[] parent, int root, int level)
        {
            for (int i = 0; i < parent.Length; ++i)
            {
                if (parent[i] == root && i != root)
                {
                    for (int j = 0; j < level; ++j)
                    {
                        Console.Write("    ");
                    }
                    Console.WriteLine("|---- " + i);
                    DFS(parent, i, level + 1);
                }
            }
        }
    }
}


1.5.3

題目

使用加權 quick-union 演算法(請見演算法 1.5)完成練習 1.5.1 。

解答

加權 quick-union 的官方實現:WeightedQuickUnionUF.java

樣例輸出:

9 1 2 3 4 5 6 7 8 9 數組訪問:3
9 1 2 3 3 5 6 7 8 9 數組訪問:3
9 1 2 3 3 5 6 7 5 9 數組訪問:3
9 1 7 3 3 5 6 7 5 9 數組訪問:3
9 7 7 3 3 5 6 7 5 9 數組訪問:5
9 7 7 3 3 7 6 7 5 9 數組訪問:3
9 7 7 9 3 7 6 7 5 9 數組訪問:5
9 7 7 9 3 7 6 7 5 7 數組訪問:9
代碼

WeightedQuickUnionUF.cs,這個類繼承了 QuickUnion.cs,重新實現了 Union() 和 Find() 等方法。

關於 QuickUnion.cs 可以參見 1.5.2 的代碼部分。

namespace UnionFind
{
    /// <summary>
    /// 使用加權 quick-union 演算法的並查集。
    /// </summary>
    public class WeightedQuickUnionUF : QuickUnionUF
    {
        protected int[] size; // 記錄各個樹的大小。

        public int ArrayParentVisitCount { get; private set; } // 記錄 parent 數組的訪問次數。
        public int ArraySizeVisitCount { get; private set; } //記錄 size 數組的訪問次數。

        /// <summary>
        /// 建立使用加權 quick-union 的並查集。
        /// </summary>
        /// <param name="n">並查集的大小。</param>
        public WeightedQuickUnionUF(int n) : base(n)
        {
            this.size = new int[n];
            for (int i = 0; i < n; ++i)
            {
                this.size[i] = 1;
            }
            this.ArrayParentVisitCount = 0;
            this.ArraySizeVisitCount = 0;
        }

        /// <summary>
        /// 清零數組訪問計數。
        /// </summary>
        public override void ResetArrayCount()
        {
            this.ArrayParentVisitCount = 0;
            this.ArraySizeVisitCount = 0;
        }

        /// <summary>
        /// 獲取 size 數組。
        /// </summary>
        /// <returns>返回 size 數組。</returns>
        public int[] GetSize()
        {
            return this.size;
        }

        /// <summary>
        /// 尋找一個結點所在的連通分量。
        /// </summary>
        /// <param name="p">需要尋找的結點。</param>
        /// <returns>該結點所屬的連通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            while (p != this.parent[p])
            {
                p = this.parent[p];
                this.ArrayParentVisitCount += 2;
            }
            this.ArrayParentVisitCount++;
            return p;
        }

        /// <summary>
        /// 將兩個結點所屬的連通分量合併。
        /// </summary>
        /// <param name="p">需要合併的結點。</param>
        /// <param name="q">需要合併的另一個結點。</param>
        public override void Union(int p, int q)
        {
            int rootP = Find(p);
            int rootQ = Find(q);
            if (rootP == rootQ)
            {
                return;
            }

            if (this.size[rootP] < this.size[rootQ])
            {
                this.parent[rootP] = rootQ;
                this.size[rootQ] += this.size[rootP];
            }
            else
            {
                this.parent[rootQ] = rootP;
                this.size[rootP] += this.size[rootQ];
            }
            this.ArrayParentVisitCount++;
            this.ArraySizeVisitCount += 4;
            this.count--;
        }
    }
}


Main 方法

using System;
using UnionFind;

namespace _1._5._3
{
    /*
     * 1.5.3
     * 
     * 使用加權 quick-union 演算法(請見演算法 1.5)完成練習 1.5.1 。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var weightedQuickUnion = new WeightedQuickUnionUF(10);

            foreach (string s in input)
            {
                weightedQuickUnion.ResetArrayCount();
                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                weightedQuickUnion.Union(p, q);
                int[] parent = weightedQuickUnion.GetParent();
                for (int i = 0; i < parent.Length; ++i)
                {
                    Console.Write(parent[i] + " ");
                }
                Console.WriteLine("數組訪問:" + weightedQuickUnion.ArrayParentVisitCount);
            }
        }
    }
}


1.5.4

題目

在正文的加權 quick-union 演算法示例中,對於輸入的每一對整數(包括對照輸入和最壞情況下的輸入),給出 id[] 和 sz[] 數組的內容以及訪問數組的次數。

解答

對照輸入和最壞輸入均在書中出現,中文版見:P146,英文版見:P229。

樣例輸出:

4 3
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 5 6 7 8 9
size:   1 1 1 1 2 1 1 1 1 1
parent visit count:3
size visit count:4

3 8
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 5 6 7 4 9
size:   1 1 1 1 3 1 1 1 1 1
parent visit count:5
size visit count:4

6 5
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 6 6 7 4 9
size:   1 1 1 1 3 1 2 1 1 1
parent visit count:3
size visit count:4

9 4
index:  0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 6 6 7 
              
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 本文目錄:1. 基礎2. I/O模型2.1 Blocking I/O模型2.2 Non-Blocking I/O模型2.3 I/O Multiplexing模型2.4 Signal-driven I/O模型2.5 Asynchronous I/O模型2.6 同步IO和非同步IO、阻塞和非阻塞的區分3. ...
  • 1》set集合:是一個無序且不重覆的元素集合;訪問速度快,解決了重覆的問題; s2 = set(["che","liu","haha"]) add():添加元素; difference():將前一個集合與後者的不同建立為一個新的集合;沒有改變當前集合,生成了新的集合; difference_upda ...
  • 一、源代碼管理 絕大多數開源軟體都是直接以源代碼形式發佈的,一般會被打包為 tar.gz 的歸檔壓縮文件。程式源代碼需要編譯為二進位可執行文件後才能夠運行使用。源代碼的基本編譯流程為: 源代碼形式的軟體使用起來較為麻煩,但是相容性和可控性較好。並且開源軟體一般會大量使用其他開源軟體的功能,所以開源軟 ...
  • 本文目錄:1. 背景2. 連接的具體過程分析 2.1 socket()函數 2.2 bind()函數 2.3 listen()函數和connect()函數 2.3.1 深入分析listen() 2.3.2 syn flood的影響 2.4 accept()函數 2.5 send()和recv()函數 ...
  • 操作系統筆記 1、批處理、分時、實時是操作系統的三種基本類型 2、分散式系統是由若幹個電腦經互連網路連接而成的,這些電腦既可以獨立工作,又能協同工作。可實現系統內的資源管理,任務動態分配,並能並行地運行分散式程式。分散式系統是網路操作系統的更高級的形式並保持了網路操作系統的全部功能。 3、核心態 ...
  • 一、系統啟動流程 一般來說,Linux 系統的啟動流程是這樣的: 1. 開機之後,位於電腦主板 ROM 晶元上的 BIOS 被最先讀取,在進行硬體和記憶體的校驗以及 CPU 的自檢沒有異常後, BIOS 將被載入到記憶體中。 2. BIOS 按照其存儲的啟動順序,依次嘗試載入含有 MBR 信息的可啟動 ...
  • 目前本人接觸過兩種模板導出的方式:(1)C#利用NPOI介面製作Excel模板,在服務端用數據渲染模板(2)在前端利用前人搭建好的框架,利用office編寫xml製作模板,在客戶端進行數據的渲染,導出的格式是word。在製作報表時兩種方式都可以滿足的基本需求,但excel模板更加強大,因為xml模板 ...
  • 首先我們知道了HTML和css用途,那麼今天就來看看HTML的一部分功能和用途。 簡單的說HTML就是靈活使用標簽,標簽就相當於一個網頁的骨架,有了這個骨架才能使網頁更能區域色彩化。 首先來說HTML術語 1.HTML文檔由許多個元素組成,所有的內容都是靠元素組織到頁面中。 2.元素的組成部分,簡單 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...