Golang语法的25个练习题：6至10题

2023-02-15

5分钟阅读时长

golang

题目6：闰年问题升级版

输入年月日，输出该日期是否是闰年，并且输出该日期是此年份的第几天

闰年判断条件：

能被4整除，并且不能被100整除
能被400整除
两个条件满足任意一个就为闰年

算法思路

接收用户输入的年月日，创建保存12个月份天数的列表
根据年份判断是否是闰年，如果是把二月份设为29天，否则把二月份设为28天
根据月份和日期统计是当年的第几天

package main

import (
	"fmt"
	"log"
	"os"
	"strconv"
)

func main() {
	year, err := input("请输入年份")
	if err != nil {
		log.Fatalln(err)
	}
	month, err := input("请输入月份")
	if err != nil {
		log.Fatalln(err)
	}
	day, err := input("请输入日期")
	if err != nil {
		log.Fatalln(err)
	}

	dateList := []int{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
	countDay := day
	if year%4 == 0 && year%100 != 0 || year%400 == 0 {
		fmt.Printf("%d年是闰年\n", year)
		dateList[1] = 29
	} else {
		dateList[1] = 28
	}
	for i := 0; i < month-1; i++ {
		countDay += dateList[i]
	}
	fmt.Printf("%d年%d月%d日是当年的第%d天", year, month, day, countDay)
}

func input(text string) (int, error) {
	fmt.Print(text)
	data := make([]byte, 1024)
	n, err := os.Stdin.Read(data)
	if err != nil {
		return 0, err
	}
	return strconv.Atoi(string(data[:n-1]))
}

题目7：猴子吃桃问题

需求分析：

猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。
第二天早上又将剩下的桃子吃掉一半，又多吃了一个。
以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。
求原来它一共摘了多少个桃子。
这题得倒着推。第10天还没吃，就剩1个，说明第9天吃完一半再吃1个还剩1个。
假设第9天还没吃之前有桃子p个
可得：p/2 - 1 = 1，得出第九天的桃子数p=4。
以此类推，即可算出第一天摘了多少桃子.

算法思路

第10天还没吃之前的桃子数量初始化p=1
从9至1循环9次，根据上述公式反推为p=(p+1)*2可得
第1天还没吃之前的桃子数量

package main

import (
	"fmt"
)

func main() {
	p := 1
	fmt.Printf("第10天还剩下%d个桃子\n", p)
	for i := 9; i >= 1; i-- {
		p = (p + 1) * 2
		fmt.Printf("第%d天还剩下%d个桃子\n", i, p)
	}
	fmt.Printf("第一天一共摘了%d个桃子\n", p)

	// output:
	//第10天还剩下1个桃子
	//第9天还剩下4个桃子
	//第8天还剩下10个桃子
	//第7天还剩下22个桃子
	//第6天还剩下46个桃子
	//第5天还剩下94个桃子
	//第4天还剩下190个桃子
	//第3天还剩下382个桃子
	//第2天还剩下766个桃子
	//第1天还剩下1534个桃子
	//第一天一共摘了1534个桃子
}

题目8：冒泡排序

冒泡排序算法由来这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列)，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”
从前到后(即从下标较小的元素开始) 依次比较相邻元素的值，若发现比后一个值大则交换位置，使值较大的元素逐渐从前移向后部。

假设有一个列表 [29 ,12 ,19 ,37 ,14] 想升序

第一轮

比较 29 > 12 交换位置
[12,29,19,37,14]
比较 29 > 19 交换位置
[12,19,29,37,14]
比较 29 > 37 不大于不交换，列表同上
比较 37 > 14 交换位置
[12,19,29,14,37]

第二轮

比较 12 > 19 不大于不交换，列表同上
比较 19 > 29 不大于不交换，列表同上
比较 29 > 14 交换位置
[12,19,14,29,37]

第三轮

比较 12 > 19 不大于不交换，列表同上
比较 19 > 14 交换位置
[12,14,19,29,37]

第四轮

比较 12 > 14 不大于不交换，列表同上
完成
[12,14,19,29,37]

package main

import (
	"fmt"
)

func main() {
	popList := []int{82, 15, 15, 41, 37, 31}
	BubbleSort(popList)
	popList = []int{29, 12, 19, 37, 14}
	BubbleSort(popList)
	// output:
	//没排序之前的列表 [82 15 15 41 37 31]
	//排好序的列表为 [15 15 31 37 41 82]
	//没排序之前的列表 [29 12 19 37 14]
	//排好序的列表为 [12 14 19 29 37]
}

func BubbleSort(popList []int) {
	count := len(popList)
	fmt.Println("没排序之前的列表", popList)
	for i := 0; i < count; i++ {
		for j := 0; j < count-i-1; j++ {
			if popList[j] > popList[j+1] { // 如果要降序就是改成 < 号
				popList[j], popList[j+1] = popList[j+1], popList[j]
			}
		}
	}
	fmt.Println("排好序的列表为", popList)
}

题目9：二分查找法

二分法是一种效率比较高的搜索方法

回忆之前做过的猜数字的小游戏，预先给定一个小于100的正整数x，让你猜，猜测过程中给予大小判断的提示，问你怎样快速地猜出来？我们之前做的游戏给定的是10次机会，如果我们学会二分查找法以后，不管数字是多少，最多只需要7次就能猜到数字

二分查找法

首先先猜50，如果猜对了，结束；如果猜大了，往小的方向猜，再猜25；如果猜小了，往大的方向猜，再猜75；…每猜测1次就去掉一半的数，这样我们就可以逐步逼近预先给定的数字.这种思想就是二分法。

二分法适用情况

必须是有序的序列。
对数据量大小有要求。
数据量太小不适合二分查找，与直接遍历相比效率提升不明显。
数据量太大也不适合用二分查找，因为数组需要连续的存储空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间

算法思路

假设有一个有序列表
[5,7,11,22,27,33,39,52,58] 请问数字11是否在此列表中，如果在它的索引值为多少？
首先我们取有序列表的中间位置 27 和 11 进行比较我们发现 11 是小于 27 的
所以我们排除 27 右边的数字
[5,7,11,22,27（排除了右边的）,33,39,52,58]
接着我们取 [5,7,11,22] 位置中间的 7 和 11 比较发现 11 是大于 7 的所以我们排除 7 左边的数字
最后我们取 11到22 的中间位置
刚好到了11 这时候就可以返回 11 的索引值了，如果没有找到就提示不存在

第一种纯算法的方式

package main

import (
	"fmt"
)

func main() {
	arrList := []int{5, 7, 11, 22, 27, 33, 39, 52, 58}
	BinarySearch(arrList, 11)
	// output:
	//数字11已找到，索引值为2
	//数字11没有找到
	//一共用了3次查找
}

func BinarySearch(arrList []int, search int) {
	count, left, right := 0, 0, len(arrList)-1
	defer func() {
		fmt.Printf("一共用了%d次查找\n", count)
	}()
	for left <= right {
		mid := left + (right-left)>>1
		count++
		if arrList[mid] < search {
			left = mid + 1
		} else if arrList[mid] > search {
			right = mid - 1
		} else {
			fmt.Printf("数字%d已找到，索引值为%d\n", search, mid)
			break
		}
	}
	fmt.Printf("数字%d没有找到\n", search)
}

第二种递归函数的方式

package main

import (
	"fmt"
)

func main() {
	arrList := []int{5, 7, 11, 22, 27, 33, 39, 52, 58}
	fmt.Println(BinarySearch(arrList, 0, len(arrList)-1, 11))
	// output: 2
}

func BinarySearch(arrList []int, left, right, search int) int {
	if left <= right {
		mid := left + (right-left)>>1
		if arrList[mid] < search {
			left = mid + 1
		} else if arrList[mid] > search {
			right = mid - 1
		} else {
			return mid
		}
		return BinarySearch(arrList, left, right, search)
	}
	return -1
}

题目10：选择排序

基本思想：从未排序的序列中找到一个最小的元素，放到第一位，再从剩余未排序的序列中找到最小的元素，放到第二位，依此类推，直到所有元素都排序完毕

若列表 [6,8,3,5,9,10,7,2,4,1]
先找到 1 最小调换
[1, 8, 3, 5, 9, 10, 7, 2, 4, 6]
接着是 2 最小调换
[1, 2, 3, 5, 9, 10, 7, 8, 4, 6]
接着是 3 最小位置不变
接着是 4 最小调换
[1, 2, 3, 4, 9, 10, 7, 8, 5, 6]
接着是 5 最小调换
[1, 2, 3, 4, 5, 10, 7, 8, 9, 6]
接着是 6 最小调换
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
接着是 7 最小位置不变
接着是 8 最小位置不变
接着是 9 最小位置不变
接着是 10 最小位置不变

package main

import (
	"fmt"
)

func main() {
	secList := []int{91, 30, 93, 98, 26, 98, 20, 90}
	SelectSort(secList)
	// output:
	//没排序之前的列表 [91 30 93 98 26 98 20 90]
	//第1轮排好序是[20 30 93 98 26 98 91 90]
	//第2轮排好序是[20 26 93 98 30 98 91 90]
	//第3轮排好序是[20 26 30 98 93 98 91 90]
	//第4轮排好序是[20 26 30 90 93 98 91 98]
	//第5轮排好序是[20 26 30 90 91 98 93 98]
	//第6轮排好序是[20 26 30 90 91 93 98 98]
	//第7轮排好序是[20 26 30 90 91 93 98 98]
	//第8轮排好序是[20 26 30 90 91 93 98 98]
	//最终排好序的列表为 [20 26 30 90 91 93 98 98]
}

func SelectSort(secList []int) {
	n := len(secList)
	fmt.Println("没排序之前的列表", secList)
	for i := 0; i < n; i++ {
		minIndex := i
		for j := i + 1; j < n; j++ {
			if secList[j] < secList[minIndex] {
				minIndex = j
			}
		}
		secList[minIndex], secList[i] = secList[i], secList[minIndex]
		fmt.Printf("第%d轮排好序是%v\n", i+1, secList)
	}
	fmt.Println("最终排好序的列表为", secList)
}

python原文：https://www.52pojie.cn/thread-1689186-1-1.html

关注公众号获得更多精彩文章

公众号：程序员大兵

Golang语法的25个练习题：6至10题

题目6：闰年问题升级版

题目7：猴子吃桃问题

题目8：冒泡排序

题目9：二分查找法

题目10：选择排序

关注公众号获得更多精彩文章

lbbniu

本页内容

相关