使用 C 和 C++ 學習、分析和實現資料結構。學習遞迴( Recursion )和排序( Sorting )
https://softnshare.com/datastructurescncpp/
遞迴c 在 軟體開發學習資訊分享 Facebook 的最佳解答
同時也有3部Youtube影片，追蹤數超過3萬的網紅李祥數學,堪稱一絕，也在其Youtube影片中提到，成為這個頻道的會員並獲得獎勵：https://www.youtube.com/channel/UCU2axN3MDyvq01LOK1umZGQ/join 追蹤我的ig：https://www.instagram.com/garylee0617/ 加入我的粉絲專頁：https://www.face...
「遞迴c」的推薦目錄：
- 關於遞迴c 在 軟體開發學習資訊分享 Facebook 的最佳解答
- 關於遞迴c 在 軟體開發學習資訊分享 Facebook 的最讚貼文
- 關於遞迴c 在 Taipei Ethereum Meetup Facebook 的精選貼文
- 關於遞迴c 在 李祥數學,堪稱一絕 Youtube 的最佳貼文
- 關於遞迴c 在 李祥數學,堪稱一絕 Youtube 的精選貼文
- 關於遞迴c 在 寶妮老師 Bonnie Youtube 的最佳解答
- 關於遞迴c 在 Re: [問題] 組合Cm取n的遞迴- 看板C_and_CPP - 批踢踢實業坊 的評價
- 關於遞迴c 在 遞迴呼叫篇| Jason note 的評價
- 關於遞迴c 在 用C語言撰寫反覆結構（for-loop）及遞迴函式（recursive）2 ... 的評價
- 關於遞迴c 在 用C 中的遞迴檢查迴文 - 他山教程 的評價
- 關於遞迴c 在 你所不知道的C 語言：遞迴呼叫篇 - Facebook 的評價
遞迴c 在 軟體開發學習資訊分享 Facebook 的最讚貼文
NT 430 特價中
擁有 C 語言的程式設計技能會給你帶來很好的職業選擇，但學習 C 語言，特別是一些比較棘手的高階東西可能真的很難。
本課程旨在使你的基本 C 語言技能更上一層樓，透過幫助你理解 C 語言程式設計的高階概念，使你能夠掌握使用高效、成熟的方法解決程式設計中的問題的藝術，從而獲得對該語言的掌握。
你將學會如何編寫高品質的 C 語言程式碼，並使自己在更高層次的程式設計職位上更有市場。
在這個 28 小時的龐大課程中，部分主題包括執行緒、函式指標、雙指標、遞迴、使用 Socket 的網路、位元操作、巨集、訊號、儲存類別和更多。
https://softnshare.com/advanced-c-programming-course/
遞迴c 在 Taipei Ethereum Meetup Facebook 的精選貼文
📜 [專欄新文章] Merkle Tree in JavaScript
✍️ Johnson
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium
這篇文章會說明 Merkle Tree 的運作原理，以及解釋 Merkle Proofs 的用意，並以 JavaScript / TypeScript 簡單實作出來。
本文為 Tornado Cash 研究系列的 Part 1，本系列以 tornado-core 為教材，學習開發 ZKP 的應用，另兩篇為：
Part 2：ZKP 與智能合約的開發入門
Part 3：Tornado Cash 實例解析
Special thanks to C.C. Liang for review and enlightenment.
本文中實作的 Merkle Tree 是以 TypeScript 重寫的版本，原始版本為 tornado-core 以 JavaScript 實作而成，基本上大同小異。
Merkle Tree 的原理
在理解 Merkle Tree 之前，最基本的先備知識是 hash function，利用 hash 我們可以對資料進行雜湊，而雜湊後的值是不可逆的，假設我們要對 x 值做雜湊，就以 H(x) 來表示，更多內容可參考：
一次搞懂密碼學中的三兄弟 — Encode、Encrypt 跟 Hash
SHA256 Online
而所謂的 Merkle Tree 就是利用特定的 hash function，將一大批資料兩兩進行雜湊，最後產生一個最頂層的雜湊值 root。
當有一筆資料假設是const leaves = [A, B, C, D]，我們就用function Hash(left, right)，開始製作這顆樹，產生H(H(A) + H(B))與H(H(C) + H(D))，再將這兩個值再做一次 Hash 變成 H(H(H(A) + H(B)) + H(H(C) + H(D)))，就會得到這批資料的唯一值，也就是 root。
本文中使用的命名如下：
root：Merkle Tree 最頂端的值，特色是只要底下的資料一有變動，root 值就會改變。
leaf：指單一個資料，如 H(A)。
levels：指樹的高度 (height)，以上述 4 個資料的假設，製作出來的 levels 是 2，levels 通常會作為遞迴的次數。
leaves：指 Merkle Tree 上的所有資料，如上述例子中的 H(A), H(B), H(C), H(D)。leaves 的數量會決定樹的 levels，公式是 leaves.length == 2**levels，這段建議先想清楚！
node：指的是非 leaves 也非 root 的節點，或稱作 branch，如上述例子中的H(H(A) + H(B)) 和 H(H(C) + H(D))。
index：指某個 leaf 所在的位置，leaf = leaves[index]，index 如果是偶數，leaf 一定在左邊，如果是奇數 leaf 一定在右邊。
Merkle Proofs
Merkle Proofs 的重點就是要證明資料有沒有在樹上。
如何證明？就是提供要證明的 leaf 以及其相對應的路徑 (path) ，經過計算後一旦能夠產生所需要的 root，就能證明這個 leaf 在這顆樹上。
因此這類要判斷資料有無在樹上的證明，類似的說法有：proving inclusion, proving existence, or proving membership。
這個 proof 的特點在於，我們只提供 leaf 和 path 就可以算出 root，而不需要提供所有的資料 (leaves) 去重新計算整顆 Merkle Tree。這讓我們在驗證資料有沒有在樹上時，不需要花費大量的計算時間，更棒的是，這讓我們只需要儲存 root 就好，而不需要儲存所有的資料。
在區塊鏈上，儲存資料的成本通常很高，也因此 Merkle Tree 的設計往往成為擴容上的重點。
我們知道 n 層的 Merkle Tree 可以存放 2**n 個葉子，以 Tornado Cash 的設計來說，他們設定 Merkle Tree 有 20 層，也就是一顆樹上會有 2**20 = 1048576 個葉子，而我們用一個 root 就代表了這 1048576 筆資料。
接續上段的例子，這顆 20 層的 Merkle Tree 所產生的 Proof ，其路徑 (path) 要從最底下的葉子 hash 幾次才能到達頂端的 root 呢？答案就是跟一棵樹的 levels 一樣，我們要驗證 Proof 所要遞迴的次數就會是 20 次。
在實作之前，我們先來看 MerkleTree 在 client 端是怎麼調用的，這有助於我們理解 Merkle Proofs 在做什麼。
基本上一個 proof 的場景會有兩個人：prover 與 verifier。
在給定一筆 leaves 的樹，必定產生一特定 root。prover 標示他的 leaf 在樹上的 index 等於 2，也就是 leaves[2] == 30，以此來產生一個 proof，這個 proof 的內容大致上會是這個樣子：
對 verifier 來說，他要驗證這個 proof，就是用裡面的 leaf 去一個一個與 pathElements 的值做 hash，上述就是 H('30', 40) 後得出 node，再 hash 一次 H('19786...', node) 於是就能得出這棵樹的 root。
重點來了，這麼做有什麼意義？它的巧思在於對 verifier 來說，他只需要儲存一個 root，由 prover 提交證明給他，經過計算後產生的 root 如果跟 verifier 儲存的 root 一樣，那就證明了 prover 所提供的資料確實存在於這個樹上。
而 verifier 若不透過 proof ，要驗證某個 leaf 是否存在於樹上，也可以把 leaves = [10, 20 ,leaf ,40]整筆資料拿去做 MerkleTree 的演算法跑一趟也能產生特定的 root。
但由 prover 先行計算後所提交的 proof，讓 verifier 不必儲存整批資料，也省去了大量的計算時間，即可做出某資料有無在 Merkle Tree 上的判斷。
Sparse Merkle Tree
上述能夠證明資料有無在樹上的 Merkle Proofs 是屬於標準的 Merkle Tree 的功能。但接下來我們要實作的是稍微不一樣的樹，叫做 Sparse Merkle Tree。
Sparse Merkle Tree 的特色在於除了 proving inclusion 之外，還可以 proving non-inclusion。也就是能夠證明某筆資料不在某個 index，例如 H(A) 不在 index 2 ，這是一般 Merkle Tree 沒辦法做到的。
而要做到 non-membership 的功能其實也不難，就是我們要在沒有資料的葉子裡補上 zero value，或是說 null 值。更多內容請參考：What’s a Sparse Merkle Tree。
實作細節
本節將完整的程式碼分成三個片段來解釋。
首先，這裡使用的 Hash Function 是 MiMC，主要是為了之後在 ZKP 專案上的效率考量，你可以替換成其他較常見的 hash function 例如 node.js 內建 crypto 的 sha256：
crypto.createHash("sha256").update(data.toString()).digest("hex");
這裡定義簡單的 Merkle Tree 介面有 root, proof, and insert。
首先我們必須先給定這顆樹的 levels，也就是樹的高度先決定好，樹所能容納的資料量也因此固定為 2**levels 筆資料，至於要不要有 defaultLeaves 則看創建 Merkle Tree 的 client 自行決定，如果有 defaultLeaves 的話，constructor 就會跑下方一大段計算，對 default 資料開始作 hash 去建立 Merkle Tree。
如果沒有 defaultLeaves，我們的樹也不會是空白的，因為這是顆 Sparse Merkle Tree，這裡使用 zeroValue 作為沒有填上資料的值，zeros 陣列會儲存不同 level 所應該使用的 zero value。假設我們已經填上第 0 筆與第 1 筆資料，要填上第 2 筆資料時，第 2 筆資料就要跟 zeros[0] 做 hash，第 2 筆放左邊， zero value 放右邊。
我們將所有的點不論是 leaf, node, root 都用標籤 (index) 標示，並以 key-value 的形式儲存在 storage 裡面。例如第 0 筆資料會是 0–0，第 1 筆會是 0–1，這兩個 hash 後的節點 (node) 會是 1–0。假設 levels 是 2，1–0 節點就要跟 1–1 節點做 hash，即可產出 root (2–0)。
後半部份的重點在於 proof，先把 proof 和 traverse 看懂，基本上就算是打通任督二脈了，之後有興趣再看 insert 和 update。
sibling 是指要和 current 一起 hashLeftRight 的值…也就是相鄰在兩旁的 leaf (or node)。
到這裡程式碼的部分就結束了。
最後，讓我們回到一開始 client 調用 merkleTree 的例子：
以及 proof 的內容：
前面略過了 proof 裡頭的 pathIndices，pathIndices 告訴你的是當前的 leaf (or node) 是要放在左邊，還是放在右邊，大概是這個樣子：
if (indices == 0) hash(A, B);if (indices == 1) hash(B, A);
有興趣的讀者可以實作 verify function 看看就會知道了！
原始碼
TypeScript from gist
JavaScript from tornado-core
參考
Merkle Proofs Explained
What’s a Sparse Merkle Tree?
延伸：Verkle Tree
Merkle Tree in JavaScript was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.
👏 歡迎轉載分享鼓掌
遞迴c 在 李祥數學,堪稱一絕 Youtube 的最佳貼文
成為這個頻道的會員並獲得獎勵：https://www.youtube.com/channel/UCU2axN3MDyvq01LOK1umZGQ/join
追蹤我的ig：https://www.instagram.com/garylee0617/
加入我的粉絲專頁：https://www.facebook.com/pg/garylee0617/
有問題來這裡發問：https://www.facebook.com/groups/577900652853942/
喜歡這支影片，記得按個"喜歡"，並且分享
訂閱就可以看到最新的影片
你最棒，記得按鈴鐺^^
高中數學重要觀念解析：https://www.youtube.com/playlist?list=PLOAKxvSm6LGkzAh5k3h-CI0-clwS7xsWm
數學思考題型：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmx__4F2KucNWpEvr1rawkw
關於數學的兩三事：https://www.youtube.com/playlist?list=PLOAKxvSm6LGlD5ABfGtLkOhNIRfWxIRc5
真的祥知道：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmQC77bAQPdl_Bw5VK8KQc-
YouTube合作影片：https://www.youtube.com/playlist?list=PLOAKxvSm6LGlQk7b-jDmCaUjJ57UMSXsf
高中數學講座：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmgafYQliX1Ewh2Ajun9NNn
學測考前猜題：https://www.youtube.com/playlist?list=PLOAKxvSm6LGko-fghK4k3eZJ23pmWqN_k
指考數甲數乙總複習https://www.youtube.com/playlist?list=PLOAKxvSm6LGlrdoVFRflK46Cm25CGvLBr
統測考前猜題：https://www.youtube.com/playlist?list=PLOAKxvSm6LGkP_Nvl8iToZUWNfOHT42Pg
抖音精選：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmoWuzdrsxoeKQBR_GgZyIk
國中會考總複習：https://www.youtube.com/playlist?list=PLOAKxvSm6LGlbMqjF4W6ElHM_lrFZijkg
遞迴c 在 李祥數學,堪稱一絕 Youtube 的精選貼文
成為這個頻道的會員並獲得獎勵：https://www.youtube.com/channel/UCU2axN3MDyvq01LOK1umZGQ/join
追蹤我的ig：https://www.instagram.com/garylee0617/
加入我的粉絲專頁：https://www.facebook.com/pg/garylee0617/
有問題來這裡發問：https://www.facebook.com/groups/577900652853942/
喜歡這支影片，記得按個"喜歡"，並且分享
訂閱就可以看到最新的影片
你最棒，記得按鈴鐺^^
高中數學重要觀念解析：https://www.youtube.com/playlist?list=PLOAKxvSm6LGkzAh5k3h-CI0-clwS7xsWm
數學思考題型：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmx__4F2KucNWpEvr1rawkw
關於數學的兩三事：https://www.youtube.com/playlist?list=PLOAKxvSm6LGlD5ABfGtLkOhNIRfWxIRc5
真的祥知道：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmQC77bAQPdl_Bw5VK8KQc-
YouTube合作影片：https://www.youtube.com/playlist?list=PLOAKxvSm6LGlQk7b-jDmCaUjJ57UMSXsf
高中數學講座：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmgafYQliX1Ewh2Ajun9NNn
學測考前猜題：https://www.youtube.com/playlist?list=PLOAKxvSm6LGko-fghK4k3eZJ23pmWqN_k
指考數甲數乙總複習https://www.youtube.com/playlist?list=PLOAKxvSm6LGlrdoVFRflK46Cm25CGvLBr
統測考前猜題：https://www.youtube.com/playlist?list=PLOAKxvSm6LGkP_Nvl8iToZUWNfOHT42Pg
抖音精選：https://www.youtube.com/playlist?list=PLOAKxvSm6LGmoWuzdrsxoeKQBR_GgZyIk
國中會考總複習：https://www.youtube.com/playlist?list=PLOAKxvSm6LGlbMqjF4W6ElHM_lrFZijkg
遞迴c 在 寶妮老師 Bonnie Youtube 的最佳解答
傳說河內的某間廟裡
有三根柱子
上面有64 個圓盤
寺廟裡有個古老的預言
當這些盤子全部按照順序被從A移動到C
世界就會滅亡
不過大家還能在這裡一起研究遞迴數列
看來盤子是還沒被移動完ww
快來和Bonnie一起
一邊玩遊戲一邊變聰明吧!!
........................................
Hello！我是Bonnie，大家最害怕的高中數學老師。
因為有感於現今網路多媒體遠比課本紙筆更有吸引力，所以決定除了在學校之外，也在網路上分享我的生活、教學、自修以及與學生相處的小心得。
如果你還是學生，你可以發現老師其實沒那麼討人厭😂如果你已經畢業，你可以在這裡找回一點青春回憶👩🎓👨🎓
Enjoy it and have a good time！
.........................................
IG: charmingteacherbonnie (Bonnie老師)
粉絲專頁: 寶妮老師
https://www.facebook.com/%E5%AF%B6%E5%A6%AE%E8%80%81%E5%B8%AB-Charming-Teacher-Bonnie-290462364959770/
遞迴c 在 遞迴呼叫篇| Jason note 的推薦與評價
以下C 程式的作用為何？ int p(int i, int N) { return (i < N && printf("%d\n", i) && ! · 延伸問題: 把 && 前後的敘述對調，是否影響輸出？ ... <看更多>
遞迴c 在 用C語言撰寫反覆結構（for-loop）及遞迴函式（recursive）2 ... 的推薦與評價
用C語言撰寫反覆結構（for-loop）及遞迴函式（recursive）2 個版本的函式，能計算出費式數列(Fibonacci Sequence): int F(int n) - solution.c. ... <看更多>
遞迴c 在 Re: [問題] 組合Cm取n的遞迴- 看板C_and_CPP - 批踢踢實業坊 的推薦與評價
※ 引述《yauhh (喲)》之銘言：
: ※ 引述《j129008 (j129008)》之銘言：
: : 問題(Question)：
: : 無法了解網路上的某篇程式
: goto ......
: : 程式碼(Code)：(請善用置底文網頁, 記得排版)
: break ......
: : void make (int now,int a,int n,int m)
: : {
: : int b=a,c;
: : if(now==m+1)
: : {
: : for(c=1; c<=m; c++)printf("%d ",way[c]);
: : printf("\n");
: : return;
: : }
: : else
: : for(b=a; b<=n; b++)
: : {
: : way[now]=b;
: : make(now+1,b+1,n,m);
: : }
: : }
: : main()
: : {
: : while(scanf("%d %d",&n,&m)==2)
: : make(1,1,n,m);
: 先看主程式呼叫 make 函數怎麼呼叫的,
: : return 0;
: : }
: : 補充說明(Supplement)：
: : 已經想破腦袋了
: : 甚至使用暴力法把程式怎麼跑的一一列出
: : 結果就是看到函式進入堆疊以後不斷的recurtion就排出答案
: : 最弄不懂的地方是make前面的兩個參數到底是怎麼做到組合的
: : 希望有人可以幫我解答一下
: 主程式先取 n m 二數,表示 C n 取 m 的意思. 這二個數字本身有意義.
: 但是卻會呼叫 make(1,1,n,m) 開始. 前面二個參數看不出意義,但是在程式執行時
: 很重要,因為那些是執行時的中繼變數.
: 從定義 void make (int now,int a,int n,int m) 看到二個變數一個叫 now,
: 另一個叫 a, 很顯然 now 是指目前函式內容中最關注的一項訊息.
: 看一下 now 在 make 函式中出現的位置.
: 1. 在 else 之後第一個 now: 操作陣列中一個位置,使那個位置存入 b, 而 b
: 可能是 a 到 n 之間的數字.
: 2. else 之後第二個 now: now 是陣列中的位置,在下一個遞迴中, now 也變成
: 下一個 now (指 now+1).
: 3. 在 if 判斷中的 now: 如果 now 是 m+1, 而 m 的意思是取 m 的意思,
: m+1 就是指 m 都取完了. 所以 now == m+1 是要結束遞迴. 結束的方法就是
: 把 way 陣列全都印出來. 而 way 陣列在前面 1. 2. 的 now 取值過程中,
: 有收集一些東西,那些東西就是答案.
: 所以看著 make 函式中的迴圈,
: 你可以想像迴圈從上往下把 way 的可能結果展開成一列一列.
: 把 way[now] = b 想像成從上往下在每一列同一個位置依序寫 a,b,c,..., 寫到 n.
: (因為迴圈設定 a 到 n 嘛)
: 然後從迴圈中二行可以看到,前面把一列的前一個位置寫了一個 b, 之後遞迴呼叫
: 一定要給一個 b+1, 顯然這個 b, 即 make 函式的參數 a, 代表一個底數.
: 也就是說 make(now, a, n, m) 意思是在 a 到 n 範圍中取 m 個數字組合,
: 而目前正在取的數字位置是 now.
: 這樣胡言亂語一番之後,不知你是否懂了?
: 假如你看懂了,接下來會發現 make 函式一個怪怪的地方是,如果 n 比 m 小......
標題應該是Cn取m才對XD
總算看懂了XD
根據我的理解，make(now,a,n,m)裡的"now"跟"a"
分別代表著Cn取m取了第幾個與目前要從哪裡開始取
所以它recurtion的方法是
ex:C5取3 代表 C5取1 + C4取1 + C3取1
->>for(b=a; b<=n; b++)
由於從loop上看，第一次可以取1~n
第二次從2~n
第三次從3~n
"now"就是代表取第幾次，所以會 1~m
"a"則是取到的內容，為避免重複所以每取一次便 +1
也就是now+1時他也要+1
所以C5取3
總共會取三次
第一次會從1取到3
第二次從2取到4
第三次從3取到5
為什麼一次只會從1取到3呢?
因為當取4時，now==4什麼也不會印
所以說造成第二次跟第三次都只會取三個 //因為每次都會前進1
但是我還是不懂要怎麼樣想到要這樣設計
我只能說如果他取到4的話那就只剩下一個數字就沒辦法做成組合了
當第一次取1時，第二次就可以從2取到4，這樣就不會重複
第二次如果取到3，第三次就可以從4取到5
我只能說這種recurtion法實在非常不直覺
能想出這種方法的人真是奇才.....
不然就是有人能提供更直覺的想法嗎?
我覺得我的理解方法似乎有些問題......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.68.131
※ 編輯: j129008 來自: 140.113.68.131 (05/04 06:52)
... <看更多>