8000 [feat]: add array.mojo iteration.mojo recursion.mojo files · coderonion/hello-algo-mojo@57156e6 · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 57156e6

Browse files
coderonioncoderonion
committed
[feat]: add array.mojo iteration.mojo recursion.mojo files
0 parents  commit 57156e6

File tree

5 files changed

+227
-0
lines changed

5 files changed

+227
-0
lines changed

‎.gitignore

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
.DS_Store
2+
.vscode/
3+
.idea/

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# Hello-Algo-Mojo
2+
- [**Mojo**](https://docs.modular.com/mojo/) programming language codes for the famous public project [krahets/hello-algo](https://github.com/krahets/hello-algo) <img src="https://img.shields.io/github/stars/krahets/hello-algo?style=social"/> about data structures and algorithms.
3+
- Go read this great open access e-book now -> [ hello-algo.com |《Hello, Algorithm》|《 Hello，算法 》](https://www.hello-algo.com/).
4+

‎chapter_array_and_linkedlist/array.mojo

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
"""
2+
File: array.mojo
3+
Created Time: 2024-03-16
4+
Author: codingonion (coderonion@gmail.com)
5+
"""
6+
7+
import random
8+
9+
fn print_array[size: Int](arr: StaticTuple[size, Int]):
10+
print_no_newline("[")
11+
for i in range(len(arr)):
12+
print_no_newline(arr[i])
13+
if i != len(arr) - 1:
14+
print_no_newline(", ")
15+
print("]")
16+
17+
fn random_access(nums: StaticIntTuple) -> Int:
18+
"""随机访问元素."""
19+
# 在区间 [0, len(nums)-1] 中随机抽取一个数字
20+
random.seed()
21+
var random_index = random.random_si64(0, len(nums) - 1)
22+
# 获取并返回随机元素
23+
var random_num = nums[random_index]
24+
return random_num
25+
26+
fn extend[enlarge: Int](nums: StaticIntTuple) -> StaticIntTuple[enlarge] :
27+
"""扩展数组长度."""
28+
# 初始化一个扩展长度后的数组
29+
var res = StaticIntTuple[enlarge]()
30+
# 将原数组中的所有元素复制到新数组
31+
for i in range(len(nums)):
32+
res[i] = nums[i]
33+
# 返回扩展后的新数组
34+
return res
35+
36+
fn insert(inout nums: StaticIntTuple, num: Int, index: Int):
37+
"""在数组的索引 index 处插入元素 num."""
38+
# 把索引 index 以及之后的所有元素向后移动一位
39+
for i in range(len(nums) - 1, index, -1):
40+
nums[i] = nums[i - 1]
41+
# 将 num 赋给 index 处的元素
42+
nums[index] = num
43+
44+
fn remove(inout nums: StaticIntTuple, index: Int):
45+
"""删除索引 index 处的元素."""
46+
# 把索引 index 之后的所有元素向前移动一位
47+
for i in range(index, len(nums) - 1):
48+
nums[i] = nums[i + 1]
49+
50+
fn traverse(nums: StaticIntTuple):
51+
"""遍历数组."""
52+
var count = 0
53+
# 通过索引遍历数组
54+
for i in range(len(nums)):
55+
count += nums[i]
56+
57+
fn find(nums: StaticIntTuple, target: Int) -> Int:
58+
"""在数组中查找指定元素."""
59+
for i in range(len(nums)):
60+
if nums[i] == target:
61+
return i
62+
return -1
63+
64+
"""Driver Code"""
65+
fn main() raises:
66+
# 初始化数组
67+
alias arr = StaticIntTuple[5](0)
68+
print("数组 arr = ", arr)
69+
alias nums = StaticIntTuple[5](1, 3, 2, 5, 4)
70+
print("数组 nums =", nums)
71+
72+
# 随机访问
73+
var random_num = random_access(nums)
74+
print("在 nums 中获取随机元素", random_num)
75+
76+
# 长度扩展
77+
var nums_new = extend[len(nums)+3](nums)
78+
print("将数组长度扩展至 8 ，得到 nums =", nums_new)
79+
80+
# 插入元素
81+
insert(nums_new, 6, 3)
82+
print("在索引 3 处插入数字 6 ，得到 nums =", nums_new)
83+
84+
# 删除元素
85+
remove(nums_new, 2)
86+
print("删除索引 2 处的元素，得到 nums =", nums_new)
87+
88+
# 遍历数组
89+
traverse(nums)
90+
91+
# 查找元素
92+
var index = find(nums, 3)
93+
print("在 nums 中查找元素 3 ，得到索引 =", index)

‎chapter_computational_complexity/iteration.mojo

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
"""
2+
File: iteration.mojo
3+
Created Time: 2024-03-16
4+
Author: codingonion (coderonion@gmail.com)
5+
"""
6+
7+
fn forLoop(n: Int) -> Int:
8+
"""For 循环."""
9+
var res = 0
10+
# 循环求和 1, 2, ..., n-1, n
11+
for i in range(1, n + 1):
12+
res += i
13+
return res
14+
15+
16+
fn whileLoop(n: Int) -> Int:
17+
"""While 循环."""
18+
var res = 0
19+
var i = 1 # 初始化条件变量
20+
# 循环求和 1, 2, ..., n-1, n
21+
while i <= n:
22+
res += i
23+
i += 1 # 更新条件变量
24+
return res
25+
26+
27+
fn whileLoopII(n: Int) -> Int:
28+
"""While 循环（两次更新）."""
29+
var res = 0
30+
var i = 1 # 初始化条件变量
31+
# 循环求和 1, 4, 10, ...
32+
while i <= n:
33+
res += i
34+
# 更新条件变量
35+
i += 1
36+
i *= 2
37+
return res
38+
39+
fn nestedForLoop(n: Int) -> String:
40+
"""双层 for 循环."""
41+
var res: String = ""
42+
# 循环 i = 1, 2, ..., n-1, n
43+
for i in range(1, n + 1):
44+
# 循环 j = 1, 2, ..., n-1, n
45+
for j in range(1, n + 1):
46+
res = res + "(" + i.__str__() + ", " + j.__str__() + "), "
47+
return res
48+
49+
"""Driver Code"""
50+
fn main() raises:
51+
var n = 5
52+
var res = forLoop(n)
53+
print("\nfor 循环的求和结果 res = ", res)
54+
55+
res = whileLoop(n)
56+
print("\nwhile 循环的求和结果 res = ", res)
57+
58+
res = whileLoopII(n)
59+
print("\nwhile 循环（两次更新）求和结果 res = ", res)
60+
61+
var res_new = nestedForLoop(n)
62+
print("\n双层 for 循环的遍历结果 ", res_new)

‎chapter_computational_complexity/recursion.mojo

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
"""
2+
File: recursion.mojo
3+
Created Time: 2024-03-16
4+
Author: codingonion (coderonion@gmail.com)
5+
"""
6+
7+
fn recur(n: Int) -> Int:
8+
"""递归."""
9+
# 终止条件
10+
if n == 1:
11+
return 1
12+
# 递：递归调用
13+
var res = recur(n - 1)
14+
# 归：返回结果
15+
return n + res
16+
17+
fn forLoopRecur(n: Int) -> Int:
18+
"""使用迭代模拟递归."""
19+
# 使用一个显式的栈来模拟系统调用栈
20+
var stack = DynamicVector[Int]()
21+
var res = 0
22+
# 递：递归调用
23+
for i in range(n, 0, -1):
24+
# 通过“入栈操作”模拟“递”
25+
stack.append(i)
26+
# 归：返回结果
27+
while len(stack):
28+
# 通过“出栈操作”模拟“归”
29+
res += stack.pop_back()
30+
# res = 1+2+3+...+n
31+
return res
32+
33+
fn tailRecur(n: Int, res: Int) -> Int:
34+
"""尾递归."""
35+
# 终止条件
36+
if n == 0:
37+
return res
38+
# 尾递归调用
39+
return tailRecur(n - 1, res + n)
40+
41+
fn fib(n: Int) -> Int:
42+
"""斐波那契数列：递归."""
43+
# 终止条件 f(1) = 0, f(2) = 1
44+
if n == 1 or n == 2:
45+
return n - 1
46+
# 递归调用 f(n) = f(n-1) + f(n-2)
47+
var res = fib(n - 1) + fib(n - 2)
48+
# 返回结果 f(n)
49+
return res
50+
51+
52+
"""Driver Code"""
53+
fn main() raises:
54+
var n = 5
55+
var res = recur(n)
56+
print("\n递归函数的求和结果 res =", res)
57+
58+
res = forLoopRecur(n)
59+
print("\n使用迭代模拟递归求和结果 res =", res)
60+
61+
res = tailRecur(n, 0)
62+
print("\n尾递归函数的求和结果 res =", res)
63+
64+
res = fib(n)
65+
print("\n斐波那契数列的第 " + n.__str__() + " 项为 " + res.__str__())

0 commit comments

Comments
 (0)
0