c++信息学培训课件.pptx

1、内容快排相关判质数筛选法 最大公约数概率上机练习字符串字符串字符串1、字符串的定义string s;/说明s是一个字符串类型的变量2、字符串的赋值string s=“abcd”;/C+语言中，字符串常量要用双引号。3、字符串的连接string s=“abc”;string t=“def”;string p=s+t;/字符串p=“abcdef”string s=“1”;string t=“2”;string p=s+t;/字符串p=”12”字符串字符串4、字符串的输入输出string s;cins;coutsendl;5、如何获取字符串的长度string s=“abcdefg”;couts.si

2、ze()endl;/输出76、如何获取字符串的某一个字符string s=“abcdef”;/字符串的字符下标是从0开始的。couts0”“s5endl;/将会输出字符 a和字符f。字符串字符串7、遍历整个字符串的字符int ans=0;string s=“abcaaba”;for(int i=0,size=s.size();i size;i+)if(si=a)ans+;coutansendl;/上面程序的功能是什么？8、如何获取字符串的子串string s=“abcdefg”;string t=s.substr(1,3);/t=“bcd”，substr函数的第1个参数表示从第几个字符开始，第

3、2个参数表示截取多少个字符，注意：字符串的字符下标是从0开始的。子串可以是空串，也是等于原串。字符串字符串9、字符串数组的定义string s3;10、字符串数组的赋值string s3;s0=“abcd”;s1=“bcdf”;s2=“cdfg”;s3=“cd”;/这是错的，下标越界。s数组的下标是从0至2。字符串字符串11、字符串数组的定义string s3;12、字符串数组的赋值string s3;s0=“abcd”;s1=“bcdf”;s2=“cdfg”;s3=“cd”;/这是错的，下标越界。s数组的下标是从0至2。13、字符串数组的读入输出string s10;for(int i=0;

4、i si;/读入第i个字符串。for(int i=0;i 10;i+)coutsis.ages.name;/读入couts.age“”s.nameendl;/输出结构体结构体5、结构体数组的定义struct Student int age;/年龄,一个整型 string name;/姓名，一个字符串;Student s2;/s变量是一个Student类型的数组。结构体结构体6、结构体数组的赋值struct Studentint age;/年龄,一个整型string name;/姓名，一个字符串;Student s2;s0.age=10;s0.name=“zhangsan”;s1.age=11;

5、s1.name=“lisi”;结构体结构体7、结构体数组的读入输出struct Studentint age;/年龄,一个整型string name;/姓名，一个字符串;Student s10;/s是一个数组，可以保存10个Student类型变量for(int i=0;isi.agesi.name;for(int i=0;i10;i+)coutsi.age”si.nameendl;快排快排快排基本数据类型整型、字符串型等结构体定义、比较函数。例题基本数据类型-整型输入100000个正整数，从小到大排序。int data1000005;for(int i=0;i ai;/读入sort(a,a+1

6、00000);/快排，从小到大排序for(int i=0;i 100000;i+)coutaiendl;/输出 快排快排基本数据类型-字符串型输入100000个学生姓名，按照字典序从小到大排序。string name100005;for(int i=0;i namei;/读入sort(a,a+100000);/快排，从小到大排序for(int i=0;i 100000;i+)coutaiendl;/输出 快排快排结构体快排有100000个学生，每个学生有总分和姓名。总分高的排名靠前；总分相同的，姓名字典序小的排名靠前。struct Student int score;/总分 string na

7、me;/姓名；Student s100005;快排快排有100000个学生，每个学生有总分和姓名。总分高的排名靠前；总分相同的，姓名字典序小的排名靠前。例题smoj 1546标题数字等都以通过点击和重新输入进行更改，顶部“开始”面板中可以对字体、字号、颜色、行距等进行修改。建议正文8-14号字，1.3倍字间距。点击此处添加题点击此处添加题判质数判质数判质数判断正整数N是否为质数写代码例题例题判质数 smoj2306筛选法筛选法筛选法筛选法求1到N之间有多少质数 smoj1452#include using namespace std;int N,ANS;int a1000010;int mai

8、n()freopen(1452.in,r,stdin);freopen(1452.out,w,stdout);cin N;int ct=0;/记录被删除的个数 for(int i=2;i*i N+1;i+)if(ai=0)/选出质数i for(int j=i+i;j N+1;_)if(_)ct+;aj=i;/筛掉i的倍数 ANS=_;cout ANS endl;return 0;例题例题分解质因子 smoj1458最大公约数最大公约数最大公约数给出两个正整数X和Y，求它们的最大公约数辗转相除法写代码例题一例题一最大公约数 smoj2307例题二例题二最大公约数II smoj2310其他练习其他

9、练习青蛙跳步 smoj1042其他练习其他练习电话号码其他练习其他练习奖励其他练习其他练习奖励例题三例题三第五题 约数 2016年南海区青少年信息学奥林匹克竞赛试题(小学甲组)smoj1199概率内容概要 一、百事世界杯之旅百事世界杯之旅-提出问题提出问题 二、学习新知-概率 三、学习新知-期望值 四、百事世界杯之旅百事世界杯之旅-解决问题解决问题百事世界杯之旅百事世界杯之旅 在在2018年年6月之前购买的百事任何饮料月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字的瓶盖上都会有一个百事球星的名字，只要凑齐所有百事球星的名字，就，只要凑齐所有百事球星的名字，就可以参加百事世界杯之旅的抽

10、奖活动可以参加百事世界杯之旅的抽奖活动，获取球星背包、随身听，还可以赴，获取球星背包、随身听，还可以赴俄罗斯观看世界杯，还不赶快行动！俄罗斯观看世界杯，还不赶快行动！庄家？玩家？庄家？玩家？连续掷连续掷4次骰子，如果都不次骰子，如果都不出现数字出现数字6，那么玩家赢，那么玩家赢，否则庄家赢。否则庄家赢。游戏规则公平吗？游戏规则公平吗？庄家？玩家？庄家？玩家？玩家用玩家用2个骰子连续掷个骰子连续掷24次次，不同时出现，不同时出现2个个6点，玩家点，玩家赢，否则庄家赢。赢，否则庄家赢。这个规则公平吗？这个规则公平吗？学习新知：概率概率概率定义：是对随机事件发生的可能性的度量。probability

11、概率是在 0,1 之间的实数生活中的实例生活中的实例掷骰子某一面出现的概率=1/6。两次和为4的概率=1/12。生活中的实例抛一次银币，出现正面的概率=1/2。抛两次银币，至少有一次正面的概率：1-1/4=3/4生活中的实例连续抽两张牌(第一次抽出的牌不放 回去)，连续得到两 A 的概率是多少？(4/54)*(3/53)理论模型理论模型 事件空间或样本空间事件空间或样本空间:S=E 随机事件随机事件A,B.：S的子集的子集 例子：掷骰子，掷例子：掷骰子，掷1次：次：S=1,2,3,4,5,6。掷掷2次和为次和为4：A=(1,3),(2,2),(3,1)注意事项如果一件事情发生的概率是1/n,不

12、是指n次事件里必有一次发生该事件,而是指此事件发生的频率接近于1/n这个数值信息学奥赛中概率的题目信息学奥赛中概率的题目 题目描述：题目描述：有一个长度为有一个长度为100米的管子，上面米的管子，上面有有 N 个可切割点，现在随机的选择个可切割点，现在随机的选择两个切割点把它切断两个切割点把它切断(每个点被选中每个点被选中的概率相同的概率相同)，问割断的管子有超过，问割断的管子有超过 L 米的概率是多少？米的概率是多少？输入文件输入文件：第一行两个数：N L 第二行：N个不相同的整数。都在1.99之间。输出文件：输出文件：一个实数。精度1e-9。数据范围：数据范围：2=N=50;1=L=100

13、 样例样例1 3 25 25 50 75 输出:1.0 样例23 50 25 50 75 输出:0.0 核心程序 double probability(vector v,int L)double tot=0;sort(v.begin(),v.end();for (int i=0;i v.size();i+)for(int j=i+1;j L|vj-vi L|100-vj L)tot+;return 2*tot/v.size()/(v.size()-1);思考“抛抛100次硬币，恰好有次硬币，恰好有30次正面向上的概率次正面向上的概率”“抛抛200次硬币，恰好有次硬币，恰好有60次正面向上的概率

14、次正面向上的概率”哪个概率大？或者相等？请凭直觉回答哪个概率大？或者相等？请凭直觉回答思考“抛抛2次硬币，恰好有次硬币，恰好有1次正面向上的概率次正面向上的概率”“抛抛4次硬币，恰好有次硬币，恰好有2次正面向上的概率次正面向上的概率”哪个概率大？或者相等？哪个概率大？或者相等？正正正正正正正正 正正正反正正正反 正正反正正正反正 正正反反正正反反 正反正正正反正正 正反正反正反正反 正反反正正反反正 正反反反正反反反 反正正正反正正正 反正正反反正正反 反正反正反正反正 反正反反反正反反 反反正正反反正正 反反正反反反正反 反反反正反反反正 反反反反反反反反生日悖论 如果一个教室里有23个或者

15、23个以上的学生，那么至少有两个学生的生日相同的概率要大于50%如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%，这是为什么呢？生日悖论生日悖论学习新知：期望值百事世界杯之旅百事世界杯之旅-解决问题解决问题题目分析 可以用倒推的方法解决这个问题。可以用倒推的方法解决这个问题。不妨假设不妨假设n=4。记记f(i)表示目前手头上已经收集到表示目前手头上已经收集到i个不同球星的个不同球星的名字，那么往后还需要平均买多少瓶饮料才能名字，那么往后还需要平均买多少瓶饮料才能凑齐所有球星的名字。凑齐所有球星的名字。显然显然f(4)=0。因为手头上已经有。因为手头上已经有4

16、个球星的名个球星的名字了，肯定不需要再买饮料了。字了，肯定不需要再买饮料了。那么那么f(3)呢？如何求？呢？如何求？倒推倒推 f(3)表示目前已经有表示目前已经有3个不同球星名字了，平均还需要买个不同球星名字了，平均还需要买多少瓶饮料才能凑齐多少瓶饮料才能凑齐4个不同球星名字。个不同球星名字。显然，此时至少需要再买显然，此时至少需要再买1瓶饮料，那么我们买瓶饮料，那么我们买1瓶饮料瓶饮料后，打开瓶盖，看看这个瓶盖写的名字是什么，有两种后，打开瓶盖，看看这个瓶盖写的名字是什么，有两种不同的可能不同的可能：（1）这个名字是之前收集到的）这个名字是之前收集到的3个球星之中的某一个。个球星之中的某一个

17、。（2）这个名字是之前从未出现过的。）这个名字是之前从未出现过的。出现第（出现第（1）种情况的概率是：）种情况的概率是：3/4 出现第（出现第（2）种情况的概率是：）种情况的概率是：1/4倒推倒推 根据前面学过的数学期望值的知识：根据前面学过的数学期望值的知识：f(3)=1+(f(3)+f(4)移项，化简后得到移项，化简后得到:f(3)=4+f(4)=4+0=4;同理同理:f(2)=1+(2/4f(2)+2/4f(3)整理得：整理得：f(2)=2+f(3)=2+4=6;f(1)=1+(1/4f(1)+3/4f(2),整理得整理得:f(1)=f(2)+4/3=6+4/3。f(0)=1+f(1)=1+6+4/3=25/3。显然，显然，f(0)就是我们需要求解的最后结果！就是我们需要求解的最后结果！动态规划 在编程时可以用动态规划来实现前面的倒推过程。