{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 3.3.1 for 循环"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"for循环一般用于<font color=Red>__循环次数可确定__</font>的情况下，一般也被称为<font color=Red>__遍历循环__</font>。 \n",
"for 语句可以依据可迭代对象中的<font color=Red>__子项__</font>，按他们的顺序进行迭代。 \n",
"这些可迭代对象包括：<font color=Red>__range__</font>、<font color=Red>__字符串__</font>、<font color=Red>__列表__</font>、<font color=Red>__集合__</font>、<font color=Red>__字典__</font>和<font color=Red>__文件对象__</font>等可迭代数据类型。 \n",
"for循环基本结构如下："
]
},
{
"cell_type": "raw",
"metadata": {},
"source": [
"for 循环变量 in 可迭代对象：\n",
" 语句块\n",
" 语句块\n",
" 语句块\n",
" 语句块\n",
" 语句块\n",
"\n",
"\n",
"\n",
" \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"需要注意，for开头的语句末尾一定是<font color=Red>__冒号结尾__</font>，其后面至少有一行语句需要在缩进的语句块中。\n",
"缩进语句块中的语句<font color=Red>__重复执行__</font>多次，直到for语句遍历完可迭代对象。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"程序执行时，从可迭代对象中逐一提取元素，赋值给循环变量，每提取一个元素执行一次语句块中的所有语句，总的<font color=Red>__执行次数__</font>由可迭代对象中<font color=Red>__元素（项）的个数__</font>确定。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 实例 4.4 等差数列前n项和 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"输入一下正整数，计算从1到这个正整数(包括该数本身)的所有整数的和。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"range(1,n+1) 可生成1，2，……，n的序列，所以等差数列前n 项和的问题，可以用range实现： \n",
"\n",
"算法描述： \n",
"1. 先设置一个初值为0的变量\n",
"2. 遍历由range()产生的整数序列 \n",
" 2.1 每得到一个整数就加到变量上\n",
"3. 输出变量的值，即为所有整数的和"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = int(input()) # 将输入的字符转成整型,例如输入 100\n",
"sum_of_i = 0 # 设累加容器初值为0\n",
"for i in range(1, n+1): # 遍历1,2,...n的数列 \n",
" sum_of_i = sum_of_i + i # 将当前项加到累加容器上，注意此处要缩进，表示循环执行\n",
"print(sum_of_i) # 输出累加总和，5050\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"这个问题也可以直接用sum()函数结合range()函数来实现。将range()函数直接作为sum()函数的参数，可以直接获得range()函数所生成序列中全部元素的和。 \n",
"例如计算从1到n的加和可以写为以下程序：\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = int(input()) # 将输入的字符转成整型,例如输入 100\n",
"print(sum(range(1, n + 1))) # sum()函数可返回序列参数的元素的和,输出 5050"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(sum(range(1, int(input()) + 1))) # sum()函数可返回序列参数的元素的和,输出 5050"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"改变range()函数中start、stop、step的值，便可以计算不同等差数列中连续n项和了。如："
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(sum(range(1, 100, 2))) # 100以内奇数的和2500\n",
"print(sum(range(0, 101, 2))) # 不超过100的偶数的和2550\n",
"print(sum(range(0, 101, 5))) # 不超过100的偶数5的整数倍的数的和1050\n",
"print(sum(range(50, 80, 5))) # 序列50 55 60 65 70 75的和为375"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 实例 4.5 计算阶乘 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1，自然数n的阶乘写作n!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"range(1,n+1) 可生成1，2，……，n的序列，阶乘是数列前n 项积的问题，可以用range实现： \n",
"\n",
"算法描述：\n",
"1. 先设置一个初值为1的变量\n",
"2. 遍历由range()产生的整数序列 \n",
" 2.1 每得到一个整数就乘到变量上\n",
"3. 输出变量的值，即为所有整数的积，也就是阶乘值"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = int(input()) # 将输入的字符转成整型,例如输入6\n",
"fact = 1 # 设阶乘初值为1，n为0时不进入循环，0的阶乘为1\n",
"for i in range(1, n + 1): # 遍历1,2,...n的数列\n",
" fact = fact * i # 将当前项加到累加容器上\n",
"print(fact) # 输出累加总和，720\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"math库中有一个用于计算阶乘的函数factorial(n)，可以调用函数简化程序设计。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"\n",
"print(math.factorial(6)) # factorial() 为计算阶乘的函数,720"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 实例 4.6 棋盘放米 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"相传古代印度国王要褒赏他的聪明能干的宰相 ，问他需要什么？ \n",
"宰相回答说：“国王只要在国际象棋的棋盘第一个格子里放1粒麦子，第二个格子里放2粒，第三个格子里放4粒，按此比例以后每一格加1倍，一直放到64格，我就感恩不尽，其他的我什么也不要了。” \n",
"请计算一下，共需多少粒麦子？按照普通大米600粒质量为50克计算，问共需麦子约多少亿吨？写出程序。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"算法描述：\n",
"1. 设定累加容器初值为0 \n",
"2. 循环获得每格的序号 i \n",
" 2.1. 计算当前格的麦粒数，为2的 i 次幂 \n",
" 2.2. 将当前格的麦粒数加到累加容器上 \n",
"3. 输出累加容器中麦粒总数 \n",
"4. 计算重量，换算单位 "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"total = 0 # 米粒总数初值\n",
"for i in range(64): # 迭代获取整数序列中的值\n",
" t = 2 ** i # 当前格中米粒数为2的i次幂\n",
" total = total + t # 累加各格中米粒数\n",
"print(total) # 输出米粒总数，18446744073709551615\n",
"\n",
"x = 50/600 # 每粒米的质量，单位为克\n",
"total_weight = total * x * 1e-3 * 1e-3 * 1e-8 # 每粒米的质量从克转为千克再转为吨再转为亿吨\n",
"print(f'总质量为{total_weight:.2f}亿吨')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# 变量t只用一次，可不定义，直接将当前格米粒数量加上即可，减少不必要的变量定义可使程序更清晰\n",
"total = 0 # 米粒总数初值\n",
"for i in range(64): # 迭代获取整数序列中的值\n",
" total = total + 2 ** i # 当前格中米粒数为2的i次幂加到当前总数上\n",
"print(total) # 输出米粒总数，18446744073709551615"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# 列表推导式方法，第6章学习\n",
"print(sum([2 ** i for i in range(64)]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 实例4.7 拉马努金法计算圆周率 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"前面提到的Leibniz公式计算圆周率的方法存在收敛慢的问题。拉马努金曾经提出过很多收敛速度极快的求π的公式，比如这个拉马努金在1914年发布的以他自己名字命名的著名公式可用于计算圆周率。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src = \"images/ch3/2.png\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"公式中的希腊字母∑，英文译音是Sigma, 表示数学中的求和号，主要用于求多项数之和，公式展开可以表示为k从0到n时各项的累加，可以用循环实现。这个公式收敛速度极快，累加3次时，就可以达到math.pi相同的精度。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from math import factorial # 导入math库中的factorial函数 用于计算阶乘\n",
"\n",
"n = int(input()) # 输入正整数表示累加项数，例如输出3\n",
"result = 0 # 累加初值为0\n",
"for k in range(n): # 重复执行n次累加\n",
" result = result + factorial(4 * k) * (1103 + 26390 * k) / (factorial(k) ** 4 * 396 ** (4 * k))\n",
"pi = 1 / (result*2 * 2 ** 0.5 / 9801) # 累加结果取倒数为圆周率值\n",
"print(pi) # 输出圆周率值，输出3.141592653589793"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"for循环可以多重嵌套使用，每增加一层循环多一层缩进，最内层循环体内的语句执行的次数为各重循环次数相乘。 \n",
"如果循环语句的循环体中又出现循环语句，就构成多重循环结构。 \n",
"for和while都支持多重循环，且可以混用。 \n",
"一般常用的有二重循环和三重循环。循环层数越多，运行时间越长，程序越复杂，<font color=Red>__最内层__</font>程序语句执行的次数是<font color=Red>__各层循环次数的乘积__</font>。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 枚举法"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 实例 4.8 百钱买百鸡 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"我国古代数学家张丘建在《算经》一书中提出的“百钱买百鸡”的数学问题，题目意思是1只公鸡5文钱、1只母鸡3文钱、3只小鸡1文钱。计算并输出有几组可能的解？\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src = \"images/ch3/3.png\" width = \"480\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"若用数学方法求解，3个未知量，只能列2个方程，不能直接求解。 \n",
"在计算机领域，这个问题可以用<font color=Red>__枚举算法__</font>求解，枚举算法的思想是： \n",
"将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，舍弃不合适的。 \n"
]
},
{
"cell_type": "raw",
"metadata": {},
"source": [
"基本思路如下：\n",
"（1）确定枚举对象、范围和判定条件。\n",
"（2）逐一枚举可能的解并验证每个解是否是问题的解。\n",
"算法步骤：\n",
"（1）确定解题的可能范围，不能遗漏任何一个真正解，同时避免重复。\n",
"（2）判定是否是真正解的方法。\n",
"（3）为了提高解决问题的效率，使可能解的范围将至最小"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"我们先用一个规模较小的问题为例。日常用的皮箱的经常是三位的密码锁，当忘记密码时，可以采用逐位猜测的方法试出来密码，我们知道，3个数字的全部组合只有1000个，所以我们试1000次一定可以找到密码。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src = \"images/ch3/4.png\" width = \"480\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"具体操作方法： \n",
"* 1.先固定第1位为0\n",
" + b. 第2位设0 \n",
" - ⅰ. 第3位从0试到9 \n",
" + c. 重复b并依次设1-9 \n",
"* 2.重复1并依次设第1位为1-9 "
]
},
{
"cell_type": "raw",
"metadata": {},
"source": [
"算法：\n",
"1.第1位数遍历从0到9的数字\n",
" 2.第2位数遍历从0到9的数字\n",
" 3.第3位数遍历从0到9的数字\n",
" 4.比较当前的三位数是否与密码相同，若相同\n",
" 5.输出当前三位数"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import random # 导入随机数模块\n",
"\n",
"keys = random.randint(100, 999) # 随机产生一个三位整数\n",
"print(keys) # 查看当前生成的随机数，每次结果不同，此处若密码为651\n",
"\n",
"for i in range(10): # 猜测百位上的数字\n",
" for j in range(10): # 猜测十位上的数字\n",
" for k in range(10): # 猜测个位上的数字\n",
" # 三个数字拼接为一个三位整数，若此三位数与随机产生的相同，则找到密码\n",
" if i * 100 + j * 10 + k == keys: \n",
" print(f'密码是{i}{j}{k}') # 密码是651"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"参考找回密码的程序，将问题规模扩大，遍历公鸡、母鸡和小鸡的数量都从1到100，一定可以找到所有正确的解。"
]
},
{
"cell_type": "raw",
"metadata": {},
"source": [
"python中的timeit()方法， 它用于获取代码的执行时间。该库将代码语句运行一百万次，并提供从集合中花费的最短时间。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%timeit\n",
"\n",
"for cock in range(1, 101): # 公鸡数量不为0且小于或等于100\n",
" for hen in range(1, 101): # 母鸡数量不为0且小于或等于100\n",
" for chicken in range(1, 101): # 小鸡数量大于0小于等于100且是3的倍数\n",
" # 鸡的总数为100，钱的总数为100\n",
" if cock + hen + chicken == 100 and 5 * cock + 3 * hen + chicken // 3 == 100 and chicken % 3 ==0 :\n",
" print(f'公鸡{cock}只，母鸡{hen}只，小鸡{chicken}只') # 遇到满足条件的数字组合就输出\n",
"\n",
"# 57.4 ms ± 3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"这是一个三重循环，最内层循环中的if语句的执行次数约为：100 * 100 * 100 = 100万次，这是一个很大的数字，计算时间开销也很大，算法的效率不高。\n",
"我们可以用“剪枝”这个方法，剪枝的思想就是<font color=Red>__剪掉不可能出现的情况，避免计算机多余的运算__</font>。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"我们可以用range(3, 101, 3)产生3的整数倍的数列，小鸡数量是3的倍数，所以可取的值一定在这个数列中。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%timeit\n",
"\n",
"# 100 * 100 * 33 = 33万次\n",
"for cock in range(1, 101): # 公鸡数量不为0且小于或等于100\n",
" for hen in range(1, 101): # 母鸡数量不为0且小于或等于100\n",
" for chicken in range(3, 101, 3): # 小鸡数量大于0小于等于100且是3的倍数\n",
" # 鸡的总数为100，钱的总数为100\n",
" if cock + hen + chicken == 100 and 5 * cock + 3 * hen + chicken // 3 == 100:\n",
" print(f'公鸡{cock}只，母鸡{hen}只，小鸡{chicken}只') # 遇到满足条件的数字组合就输出\n",
"\n",
"# 20.7 ms ± 626 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"实际上当公鸡和母鸡数量x, y 确定的情况下，小鸡的数量 z 可由100 – x - y计算，并不需要用循环进行遍历。可将其用两重循环实现求解，此时，最大循环次数为10000次，效率提高33倍。"
]
},
{
"cell_type": "raw",
"metadata": {},
"source": [
"python中的timeit()方法用于获取代码的执行时间。该库将代码语句运行一百万次，并提供从集合中花费的最短时间。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# %%timeit\n",
"\n",
"# 100 * 100 = 1万次\n",
"for cock in range(1, 101): # 公鸡数量不为0且小于或等于100\n",
" for hen in range(1, 101): # 母鸡数量不为0且小于或等于100\n",
" chicken = 100 - cock - hen # 小鸡数量可由公鸡和母鸡数量计算得到\n",
" if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100:\n",
" print(f'公鸡{cock}只，母鸡{hen}只，小鸡{chicken}只') # 遇到满足条件的数字组合就输出\n",
" \n",
"# 1.35 ms ± 41.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"由于要求每种鸡数量都不能为0，所以公鸡最多只能买19只，母鸡最多只能买32只，这样继续裁剪，减少外面两层循环的次数："
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%timeit\n",
"\n",
"# 19 * 32 = 608次\n",
"for cock in range(1, 20): # 公鸡数量不超过20\n",
" for hen in range(1, 33): # 母鸡数量不超过33\n",
" chicken = 100 - cock - hen # 小鸡数量可由公鸡和母鸡数量计算得到\n",
" if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100:\n",
" print(f'公鸡{cock}只，母鸡{hen}只，小鸡{chicken}只') # 遇到满足条件的数字组合就输出\n",
" \n",
" \n",
"# 88.7 µs ± 5.1 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"从结果中可以发现这样的一个规律： \n",
"公鸡是4的倍数，母鸡是7的递减率，小鸡是3的递增率，为了确认这一规律，数学上推导一下这个不定方程： \n",
"x + y + z = 100 \n",
"5x + 3y + z/3 = 100 \n",
"消去z可得：7x + 4y = 100 \n",
" \n",
"由此可得： \n",
"y = 25 - (7/4)x \n",
"z = 75 + (3/4)x \n",
"因为0 < y < 100，且是自然数，则可得知 x 必为4的整数倍的正整数才能保证y 和 z 都是整数； \n",
"x 最大值必小于16 才能保证y 值为正数。 \n",
"所以x值只能取4、8、12。这样只循环3次就可以找到所有可能的解。 \n",
"可以继续优化代码提高效率："
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%timeit\n",
"\n",
"for cock in range(4, 16, 4): # cock 初值为4，小于16，步长为4\n",
" hen = 25 - cock // 4 * 7 # 整除“//”符号保证运算结果仍为整数\n",
" chicken = 75 + cock // 4 * 3\n",
" print(f'公鸡{cock}只，母鸡{hen}只，小鸡{chicken}只') # 遇到满足条件的数字组合就输出\n",
"\n",
"# 15.9 µs ± 518 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"尽可能减少循环嵌套的层数，让代码趋于<font color=Red>__扁平__</font>，使逻辑更简单，更容易阅读、理解和维护代码。需多重循环求解时，可以将内层循环的功能定义成<font color=Red>__函数__</font>，将二重循环转换为两个一重循环，使代码逻辑更清晰。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 迭代法"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。\n",
"迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。\n",
"比较典型的迭代法如“二分法”和\"牛顿迭代法”属于近似迭代法。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 兔子繁殖问题"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"兔子从出生后第3个月起每个月都会生一对兔子，小兔子成长到第三个月后每个月又会生一对兔子。初始有一对小兔子，假如兔子都不死，用户输入一个月份数，计算并在一行内输出从1到n月每个月的兔子数量。\n",
"各月的兔子数量形成的数列是： \n",
"1，1，2，3，5，8，13，…… \n",
"斐波那契数列以如下被以递推的方法定义： \n",
"F(1)=1 \n",
"F(2)=1 \n",
"F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*） \n",
"计算a，b指向数据的和作为新的一项，同时将变量b指向新产生的数据项，将变量a指向倒数第二项，也就是原来变量b指向的那个数据，这个操作可以用同步赋值语句a,b=b,a+b实现。\n",
"\n",
"<img src = \"images/ch3/5.gif\">"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = int(input()) # int()将input()接收的字符串转整数,例如输入12\n",
"a, b = 1, 1 # 设定数列前两项的初值\n",
"for i in range(n): # i 只用于控制循环次数,n值为12\n",
" print(a, end=' ') # 每次循环输出一个值，不换行\n",
" a, b = b, a + b # 迭代，b的值赋给a，把a，b的和赋值给b\n",
"# 1 1 2 3 5 8 13 21 34 55 89 144"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 迭代法开平方"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"求平方根的迭代公式： \n",
"x1=1/2*(x0+a/x0） \n",
"算法： \n",
"1.先自定一个初值x0，作为a的平方根值，在我们的程序中取a/2作为x0的初值；利用迭代公式求出一个x1。此值与真正的a的平方根值相比，误差很大。 \n",
"2.把新求得的x1代入x0中，准备用此新的x0再去求出一个新的x1.\n",
"3.利用迭代公式再求出一个新的x1的值，也就是用新的x0又求出一个新的平方根值x1，此值将更趋近于真正的平方根值。\n",
"4.比较前后两次求得的平方根值x0和x1\n",
" 4.1 如果它们的差值小于我们指定的值，即达到我们要求的精度，则认为x1就是a的平方根值，去执行步骤5；\n",
" 4.2 否则执行步骤2，即循环进行迭代。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"\n",
"\n",
"x = int(input()) # 输入整数\n",
"x0 = x / 2 # 初值\n",
"x1 = (x0 + x / x0) / 2 # 迭代公式\n",
"while True: # 迭代精度\n",
" x0 = x1\n",
" x1 = (x0 + x / x0) / 2\n",
" if abs(x0 - x1) < 1e-5:\n",
" break\n",
"print(x1) # 2.23606797749979\n",
"print(math.sqrt(x)) # 2.23606797749979"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 牛顿迭代法 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src = \"images/ch3/6.gif\">\n",
"牛顿迭代法解下列方程的解： \n",
"$$ x ^ 4 - 3 * x ^ 3 + 1.5 * x ^ 2 + -4 = 0 $$\n",
"\n",
"牛顿迭代法是一种可以用来快速求解函数零点的方法，关键问题：切线是曲线的线性逼近。\n",
"牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。\n",
"在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# 定义初始值和参数\n",
"x0 = 0.2\n",
"max_iter = 50\n",
"tol = 1e-5\n",
"\n",
"# 开始迭代\n",
"for i in range(max_iter):\n",
" # 计算f(x)和f'(x)\n",
" fx = x0 ** 4 - 3 * x0 ** 3 + 1.5 * x0 ** 2 + -4\n",
" fx_first_order = 4 * x0 ** 3 - 9 * x0 ** 2 + 3 * x0\n",
"\n",
" # 计算新的x值\n",
" x = x0 - fx / fx_first_order\n",
"\n",
" # 检查是否满足精度要求\n",
" if abs(x - x0) < tol:\n",
" print(f'经{i}次迭代，估计参数值是{x}')\n",
" break\n",
"\n",
" # 更新x0\n",
" x0 = x\n",
"else:\n",
" print('达到最大迭代次数，无法收敛')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def f(x):\n",
" \"\"\"f的方程\"\"\"\n",
" return x ** 4 - 3 * x ** 3 + 1.5 * x ** 2 + -4\n",
"\n",
"\n",
"def f_first_order(x):\n",
" \"\"\"f的一阶导数\"\"\"\n",
" return 4 * x ** 3 - 9 * x ** 2 + 3 * x\n",
"\n",
"\n",
"def get_root(x0, max_iter=50, tol=1e-5):\n",
" \"\"\"将初始值浮点化\"\"\"\n",
" p0 = 0.2 # 初始化迭代值\n",
" for i in range(max_iter):\n",
" p = p0 - f(p0) / f_first_order(p0) # f的一阶导数不能为0\n",
" if abs(p - p0) < tol: # 如果小于精度值则退出迭代\n",
" return f'经{i}次迭代，估计参数值是{p}'\n",
" p0 = p\n",
" print('达到最大迭代次数，无法收敛')\n",
"\n",
"\n",
"if __name__ == '__main__':\n",
" print(get_root(0)) # 经12次迭代，估计参数值是2.648936536182061\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 蒙特卡洛模拟"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"蒙特卡洛（Monte Carlo）方法是由数学家冯·诺伊曼提出的，诞生于上世纪40年代美国的“曼哈顿计划”。蒙特卡洛是一个地名，位于赌城摩纳哥，象征概率。蒙特卡洛方法的原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 蒙特卡洛法计算圆周率"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"用蒙特卡洛方法计算圆周率π的原理如下：一个边长为2r的正方形内部相切一个半径为r的圆，圆的面积是πr2，正方形的面积为4r2，二者面积之比是π/4，因为比值与r大小无关，所以可以假设半径 r的值为1。 \n",
"<img src = \"images/ch3/7.png\"> \n",
"\n",
"在这个正方形内部，随机产生n个点，坐标为（x,y），当随机点较多时，可以认为这些点服从均匀分布的规律。计算每个点与中心点的距离是否大于圆的半径(x2+y2>r2)，以此判断是否落在圆的内部。统计圆内的点数c，c与n的比值乘以4，就是π的值。理论上，n越大，计算的π值越准，但由于随机数不能保证完全均匀分布，所以蒙特卡洛法每次计算结果可能不同。 编程实现用蒙特卡洛方法计算π值，为了自动测评的需要，请先读入一个正整数sd作为随机数种子，并要求使用 x,y = random.uniform(-1,1) , random.uniform(-1,1) 语句来生成随机点的坐标值。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"\n",
"\n",
"# 输入正整数，表示产生点数量\n",
"times = int(input())\n",
"\n",
"# 计数器，落在圆内的点数，初值为0\n",
"hits = 0\n",
"for i in range(times):\n",
" x, y = random.uniform(-1, 1), random.uniform(-1, 1)\n",
" # 计算坐标（x,y）到原点的距离，小于半径则在圆内\n",
" if x**2 + y**2 < 1:\n",
" hits += 1\n",
"# 计算并输出圆周率值，浮点数\n",
"pi = (hits / times) * 4\n",
"print(pi)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 蒙特卡洛法计算百钱百鸡问题"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"\n",
"\n",
"def monte_carlo_cock(num):\n",
" answer = []\n",
" for i in range(num):\n",
" hen = random.randint(1, 20)\n",
" cock = random.randint(1, 33)\n",
" chicken = 100 - cock - hen\n",
" if chicken % 3 == 0 and 5 * cock + 3 * hen + chicken // 3 == 100 :\n",
" group = [cock, hen, chicken]\n",
" if group not in answer:\n",
" answer.append(group)\n",
" return answer\n",
"\n",
"\n",
"if __name__ == '__main__':\n",
" result = monte_carlo_cock(10000)\n",
" for x in result:\n",
" print('公鸡{}只，母鸡{}只，小鸡{}只'.format(*x))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 实例 4.9 圆周率查询统计"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"数据文件下载：\n",
"[3200wpi.txt](https://data.educoder.net/api/attachments/4784494?type=text/plain)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"圆周率日是一年一度的庆祝数学常数π的节日，时间被定在3月14日。通常是在下午1时59分庆祝，以象征圆周率的六位近似值3.14159，有时甚至精确到26秒，以象征圆周率的八位近似值3.1415926；习惯24小时记时的人在凌晨1时59分或者下午3时9分（15时9分）庆祝。全球各地的一些大学数学系在这天举办派对。\n",
"\n",
"由于圆周率小数位是无限的，那么，这里面会不会出现任意的数字组合呢？我们的生日、密码之类的数字能不能在圆周率中找到呢？\n",
"\n",
"事实上，较短的数字组合很容易在圆周率中找到，而且还会重复出现多次，例如，000000第一次出现在1,699,927位，第二次出现在2,328,783位。123456首次出现于第2,458,885位，第二次出现于第3,735,793位。任意的6位数字组合，都出现在圆周率小数位的前1500万。\n",
"\n",
"据说圆周率中能找到所有人生日、银行卡密码和手机号，尝试一下，看你的生日或手机号在圆周率前3000万位中是否存在？"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"birthdate = input() # 输入自己的生日或其他字符串\n",
"n = len(birthdate) # 获取输入的字符串的位数\n",
"pi = open('/data/bigfiles/3200wpi.txt').read() # 读取文件中的圆周率为字符串\n",
"# print(len(pi)) # 去掉注释可输出文件中圆周率位数\n",
"for i in range(len(pi)): # 逐个遍历圆周率中的字符序号\n",
" if birthdate == pi[i: i + n]: # 如果从当前字符向后的n个字符构成的字符串与输入的字符串相同\n",
" print(i, i + n) # 输出这个字符串的起止位置序号\n",
" # print(pi[:i + n]) # 输出到匹配字符串为止的圆周率，此语句在本地运行，不要在平台上运行\n",
" # break # 若去掉注释，匹配到一个就终止循环"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"输入：\n",
"5201314\n",
"输出：\n",
"2823258 2823265\n",
"25808025 25808032\n",
"26170648 26170655\n",
"\n",
"输入\n",
"13297966265\n",
"输出：\n",
"22822747 22822758"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a, b, c, d, e = 0, 0, 0, 0, 0 # 累加器清0\n",
"pi = open('/data/bigfiles/3200wpi.txt').read() # 读取文件中的圆周率为字符串\n",
"for i in pi: # 逐个遍历圆周率中的字符序号\n",
" if i == '0':\n",
" a = a + 1\n",
" elif i == '1':\n",
" b = b + 1\n",
" elif i == '2':\n",
" c = c + 1\n",
" elif i == '3':\n",
" d = d + 1\n",
" elif i == '4':\n",
" e = e + 1\n",
" \n",
"# 分别统计输出0，1，2，3，4的数量\n",
"print(a, b, c, d, e)\n",
"# 3355091 3355566 3356627 3355076 3357258\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 读文件统计成绩平均值"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"\n",
"<a href = \"https://images/ch3/his.txt\"> his.txt "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fr = open('images/ch3/his.txt') # 打开文件，创建一个可遍历的文件对象\n",
"\n",
"total_score = 0 # 总成绩置0\n",
"count = 0 # 计数器置0\n",
"for score in fr: # 遍历文件，每次取到文件中的一行，字符串类型\n",
" total_score = total_score + float(score) # 字符串的成绩转数值类型，加到总成绩上\n",
" count = count + 1 # 成绩数量计数\n",
"avg_score = total_score / count # 计算平均成绩\n",
"\n",
"print(avg_score)\n",
"print(f'{avg_score:.2f}') # 格式化输出\n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
