打卡第十五天

1.按要求输出序列

问题描述

明明的爸爸是一位著名的数学家。他在明明很小的时候就发现明明有过人的数学天赋，因此有意培养他对数学的兴趣。一次，明明的爸爸为了培养明明对数字的敏感，和明明玩起了一个数字游戏，这个游戏的名称叫“按要求输出序列”。在游戏中，明明的爸爸给了明明一串数字，要求明明首先把这串数字中重复出现的数字删除到仅剩一个，即相同的数字只保留一个，然后将这串数字从小到大进行排序。明明很快就理解了游戏的规则，开始玩起来。明明的爸爸首先给了明明三个数字：3、2、1；明明很快就回答说：“1、2、3”。明明的爸爸惊讶于明明的反应能力，开始加大游戏的难度，给出了由6个数字组成的数字串：2、1、4、3、5、2；明明眼珠子一转，脱口而出：“1、2、3、4、5”（由于“2”出现了两次，因此要删除一个，然后再排序输出。）。明明的爸爸意识到简单的数字串难不住明明，于是决定给出很长的一串数字串来考明明。但与此同时，明明爸爸面对这很长的数字串也无法一时计算出最后的结果，于是就求助于你，让你帮他写一个程序，用来计算出数字串最后的结果。

明明的爸爸的问题可以归结为：给你一个数字串，里面有n个数字，首先对数字串中的数字进行处理，删除重复出现的数字（重复出现的数字只保留一个），然后对数字串从小到大进行排序，最后输出排序后的字符串。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据占两行：

第一行是一个正整数n（1≤n≤200），表示数字串中有n个数字，

第二行是n个数字，n个数字都大于等于0且小于等于10^9，每两个数字用一个空格隔开。

每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个排序后的数字串，数字串中的数字用一个空格隔开。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

个人总结

先排序，后用unique进行去重

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n; while(cin>>n){ vector<int> num(n); for(int i=0;i<n;i++){ cin>>num[i]; } sort(num.begin(),num.end()); //排序 num.erase(unique(num.begin(),num.end()),num.end()); //去重 for(int i=0;i<num.size()-1;i++){ cout<<num[i]<<" "; } cout<<num.back()<<endl; } return 0; }

2.部落人乘法

问题描述

明明热爱数学，他的爸爸也有意培养明明对数学的兴趣。

一次，为了拓展明明的知识面，爸爸给明明讲了一个原始部落人计算乘法的方法：

据说原始部落人以小石子作为计算工具，并用减半和加倍两种运算就能求得任何两个整数的乘积。

其规则是：

左边不断除2，写下商，舍去余数；

右边不断加倍，直到左边变成1为止。

取结果的方法是：

如果某行左边是偶数，就划去整个这一行；

如果某行左边是奇数，右边剩下的数相加即可。

例如求13与15的乘积的过程是：

计算过程：

13--------15 ：13除以2等于6，舍去余数1，15乘以2等于30；

6---------30 ：6除以2等于3，30乘以2等于60；

3---------60 ：3除以2等于1，舍去余数1，60乘以2等于120；

1---------120 ：左边数字为1，停止计算。

取结果过程：

13--------15 ：左边是奇数，取15；

6---------30 ：左边是偶数，划去；

3---------60 ：取60；

1---------120 ：取120；

其结果就是： 13*15=15+60+120=195。

明明对爸爸讲的这个故事相当感兴趣，也自己动手开始模拟上面的过程计算起来。刚开始的时候，明明感觉这样计算很有趣，但是时间一长，明明就觉得这样的计算过程很麻烦。他想让你帮他写一个程序，快速的计算出上述乘法最后相加的式子和结果。

明明的问题可以归结为：给你两个整数，使用上面描述的乘法过程，输出最后的相加的式子。

输入说明

你的程序需要从标准输入设备（通常为键盘）中读入多组测试数据。每组测试数据占一行，其中包含两个整数a和b（1 <= a, b <= 100）。

输出说明

对每组测试数据，你的程序需要向标准输出设备（通常为启动该程序的终端）依次输出一组对应的答案。格式参见样例。

个人总结

#include <iostream> #include <vector> using namespace std; int main(){ int a,b; while(cin>>a>>b){ int shang=a; int factor=b; int result=a*b; vector<int> number; if(shang%2!=0) number.push_back(factor); while(shang!=1){ shang=shang/2; factor*=2; if(shang%2!=0){ //若 左边的数为奇数,将右边的数放入number数组中 number.push_back(factor); } } cout<<a<<"*"<<b<<"="; for(int i=0;i<number.size()-1;i++){ cout<<number[i]<<"+"; } cout<<number.back()<<"="<<result<<endl; } return 0; }

3.序列

问题描述

明明的爸爸经常用做游戏的方法启发明明对数学的兴趣。有一次，明明爸爸准备了许多盒子和球，他要和明明做一个放球的游戏。

游戏如下：要将k个小球依次装入到若干个盒子中去（可以使用的盒子数不限）。

小球装入盒子的规则如下：

1）第一个盒子不能为空。

2）依次装入各个盒子的球数必须严格递增。例如：当k=8时，装入方法有1，2，5或1，3，4。

3）装入的盒子数尽可能多。

4）所有相邻盒子的球数之差的绝对值之和最小。

如上例中：装入法1，2，5，则差的绝对值之和为(2-1)+(5-2)=4。装入法1，3，4，则差的绝对值之和为(3-1)+(4-3)=3。因此应该采用后一种装法。

明明明白了规则以后，就兴致盎然地玩起了游戏。起先明明玩得很有劲，每次都能顺利的找出最佳的装小球的方法。但是随着小球数量的增多，装小球的方法也就变得越来越多，明明就需要花更多的时间才能找到最佳的装球方法，这使得明明有些犯难了。于是明明想到了你，他想请你帮他写一个程序，他把小球的数量告诉你，而你的程序用来计算装小球的方法。

明明的问题可以归结为：告诉你小球的数量k，然后通过程序计算出盒子装小球的最佳方法。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行有一个整数k（1 ≤k ≤10000），即小球的个数。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一串整数，即表示依次放入各个盒子里的小球的个数，每两个数字之间用一个‘,’分隔。每组运算结果单独占一行，其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。

个人总结

贪心算法

1.满足“盒子最多”且“严格递增”：最极限的装法：1，2，3，...，m

只需要找到一个最大的盒子数m，使得这m个盒子的球数总和刚好<=k。

2.满足“相邻差的绝对值之和最小”：“相邻差的绝对值之和”等于最后一个盒子的球数减去第一个盒子的球数。

为了让这个差值最小，需要把剩下的球从后往前，依次给每个盒子加 1 个。这样既能保证序列依然严格递增，又能让最大值增加得最少，使得前后差值保持最小。

#include <iostream> #include <vector> using namespace std; int main(){ int k; while(cin>>k){ //寻找最大的盒子数 m int m=1; int sum=0; while(sum+m<=k){ // 只要当前的球数总和加上下一个需要的球数不超标，就可以继续增加盒子 sum+=m; m++; } m--; vector<int> box(m); for(int i=0;i<m;i++){ box[i]=i+1; } int remain=k-sum; for(int i=m-1;i>=0&&remain>0;i--){ box[i]++; remain--; } for(int i=0;i<m;i++){ cout<<box[i]; if(i<m-1){ cout<<","; } } cout<<endl; } return 0; }

4.双重回文数

问题描述

如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做回文数。例如，12321就是一个回文数，而77778就不是。当然，回文数的首和尾都应是非零的，因此0220就不是回文数。事实上，有一些数（如21），在十进制时不是回文数，但在其它进制（如二进制时为10101）时就是回文数。 编一个程序，从文件读入两个十进制数 N (1<= N <= 15) S (0 <S <10000) 然后找出前N个满足大于S且在两种或两种以上进制（二进制至十进制）上是回文数的十进制数，输出到文件上。 本问题的解决方案不需要使用大于4字节的整型变量。

输入说明

只有一行，用空格隔开的两个数N和S。

输出说明

N行, 每行一个满足上述要求的数，并按从小到大的顺序输出。

个人总结

#include <iostream> #include <string> #include <algorithm> using namespace std; // 判断字符串是否为回文 (双指针法) bool func(const string& s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } //将十进制转为x进制 string trans(int num,int x) { string result = ""; // 除基取余 while (num > 0) { result += (char)('0' + (num % x)); num /= x; } return result; } int main(){ int n,s; cin>>n>>s; int num=s+1; int count=0; //表示满足条件的数的个数 //遍历大于s的num while(num>s){ //判断 num是否满足在两种或两种以上进制上是回文数 int m=0; //该数字在m种进制上为回文数 for(int i=2;i<=10;i++){ string str=trans(num,i); if(func(str)) m++; if(m>=2) break; } if(m>=2){ cout<<num<<endl; count++; } if(count==n) break; num++; } return 0; }

5.等差数列

问题描述

一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...) 在这个问题中a是一个非负的整数，b是正整数。

写一个程序来找出在双平方数集合S中长度为n的等差数列。双平方数集合是所有能表示成p2＋q2的数的集合。

输入说明

第一行: N(3<= N<=25),要找的等差数列的长度。 第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。

输出说明

如果没有找到数列,输出`NONE'。

如果找到了，输出一行或多行, 每行由两个整数组成:a,b 这些行应该先按b排序再按a排序(均为升序)。

将不会有多于10,000个等差数列。

个人总结

1.剪枝优化：1.算出b的最大可能值 2.找a时，若发现a加上整个数列的跨度已经超出了总上限，立马break放弃当前循环，去试下一个更大的公差b

2.因为n=0时，数列中只有a，为了满足题目条件，a必须是双平方数，可以直接从bisquares中取数，省时间

3.外层循环找b，内层循环找a，自然形成题目要求的排序顺序

4.将所有算出的双平方数位置标记为true 以后查任何数字，只需 O(1) 的时间就知道是不是双平方数

#include <iostream> #include <vector> using namespace std; int main() { int N, M; cin>>N>>M; int max_val = M * M * 2; // 双平方数的最大上限 vector<bool> is_bisquare(max_val + 1, false); //判断是否为双平方数 vector<int> bisquares; // 算双平方数，若是则记为true for (int p = 0; p <= M; p++) { for (int q = 0; q <= M; q++) { is_bisquare[p * p + q * q] = true; } } //把在范围内的双平方数放入bisquares数组 for (int i = 0; i <= max_val; i++) { if (is_bisquare[i] == true) { bisquares.push_back(i); } } bool found = false; // 记录是否找到过答案 // 外层循环找b，内层循环找a int max_b = max_val / (N - 1); // 公差 b 的最大可能值 for (int b=1; b<=max_b;b++) { //找b for (int i=0;i<bisquares.size();i++) { //找a int a=bisquares[i]; //a一定得是双平方数 if (a+(N-1)*b>max_val) { break; } bool ok=true; for(int k=1;k<N;k++) { if (is_bisquare[a+k*b] == false) { ok = false; break; // 只要有一个不是双平方数，直接淘汰这个组合 } } if (ok) { cout <<a<<" "<<b<<endl; found = true; } } } if (found == false) { cout << "NONE" << endl; } return 0; }

单词打卡

英语翻译

III. 硬件

现代数字计算机在概念上都很相似，无论体积大小。不过，根据成本和性能，它们可以分为几类： 个人计算机（微型计算机）：成本相对较低，通常是台式机尺寸（不过“笔记本电脑”小到可以放进公文包，“掌上电脑”则能装进口袋）；工作站：具备增强图形和通信能力的微型计算机，特别适合办公场景；小型计算机：通常价格过高，不适合个人使用，其性能更适配企业、学校或实验室；大型计算机：体积庞大、价格昂贵，能够满足大型企业、政府部门、科研机构等的需求（其中最大、最快的被称为超级计算机）。

数字计算机并非单一机器，而是由五个独立部分组成的系统：（1） 中央处理器（CPU）（2） 输入设备（3）存储设备（4）输出设备（5）通信网络（总线）：用于连接系统的所有部件，并将系统与外部世界相连。