算法刷题的基础（一）——必会的算法基础知识

2023-08-07 10:34:34

一、应对算法刷题网站的输入要求

1.不知道输入什么时候结束怎么办？

比如：

PAT 1002：读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

你根本不知道输入的正整数有多长，你该怎么办？

法一：while……EOF型

while(scanf("%d",&n)!=EOF){
	……
}

代码意思为：读取文件时没有读到文件末尾便一直循环。反复读入n，执行循环体的内容。

scanf是通用的，字符串（%s）或数字（%d)都可以.如果只是字符串的话还可以用gets()和getchar()。

while(gets(str)!=NULL){
	……
}

char ch=getcahr();
while(ch!='\n'){
        ……
        ch=getchar();
    }

意思就是你输入一串字符放入缓存区（按回车键表示输入结束），你写一次ch=getchar()，ch就从缓存区拿一个字符，只要遇到结束标志\n。

2.知道输入何时结束的最简结构：

比如循环要执行T次，则可以写成：

while(T--){
	……
}

二、入门篇——入门模拟

简单模拟、查找元素、图形输出过于简单，不作讲解。

下面讲下日期处理、进制转换、字符串处理。

日期处理：给定两个日期，如何求他们之间差多少天？

思路分析：如果按照一般数学思路，就会考虑闰年平年31天28天等情况，如果按照计算机思维，放个计数器，设置好进位，让前面的日期不断加一，等于后面的日期时停止，记录加一的次数，就是他们之间相隔的天数。

进制转换：一个P进制数如何转化为Q进制数。（P、Q<=10）

思路分析：分两步，第一步是将P进制数转化为10进制数，第二步是将10进制数转为Q进制数。

1.P进制数转化为10进制数

对于一个十进制数y=d1d2d3d4……dn，可以写成这个形式：

对于一个P进制数y=d1d2d3d4……dn，可以写成这个形式：

而这个公式很容易用循环实现：

int y=0,product=1;
while(x!=0){
	y=y+(x%10)*product;
	x/=10;
	product=product*P;
}

2.10进制数转为Q进制数

除基取余代码：10进制数y转为Q进制数

int z[40],num=0;
do{
	z[num++] = y % Q;
	y = y / Q;
} while(y!=0)

字符串处理：读入一串字符，判断是否是回文数。

思路分析：从下标0开始遍历，到len/2前为止（比如10个数，到4就好了，然后遍历下标为01234，比如9个数，到3就好了，遍历下标为0123,中间的5不考虑，然后后面6789与前面对应）。

然后只需判断str[i]和str[len-1-i] 是否相等即可。

排序重要思想：

题目：某小学最近得到一笔赞助，打算拿出其中一部分为成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课成绩：语文、数学、英语。如果两个同学总分相同，按语文从高到低进行排序，如果总分和语文都相同，则按规定学号小的同学排在前面。根据以上要求，编程实现其功能。

思路分析：利用好algorithm头文件中的sort函数，自写一个cmp函数，该函数内用条件语句生搬硬套满足题意即可。

#include<iostream>
#include<algorithm>
using namespace std;

struct score {
	int chinese;
	int math;
	int english;
	int num;
};
bool cmp(score x, score y) {//这招niubi
	if (x.chinese + x.math + x.english != y.chinese + y.math + y.english)
		return x.chinese + x.math + x.english > y.chinese + y.math + y.english;
	else {
		if (x.chinese != y.chinese) {
			return  x.chinese > y.chinese;
		}
		else
			return x.num < y.num;
	}
}

int main() {
	score a[1000];
	int N;
	cin >> N;//输入学生个数
	for (int i = 0; i < N; i++) {
		cin >> a[i].chinese >> a[i].math >> a[i].english;//按照语数英的顺序输入成绩
		a[i].num = i;
	}
	sort(a, a + N, cmp);
	for (int i = 0; i < N; i++) {
		cout << a[i].chinese << " " << a[i].math << " " << a[i].english << " " << a[i].num <<" " << a[i].chinese + a[i].math + a[i].english<<endl;
	}
	return 0;
}

约瑟夫环：

题目：【问题描述】有n张牌，记为1，2，3，…,n（n<1000）,应当怎样排放，才能使打开第一张是1，然后把两张依次放到末尾；打开上面一张刚好是2，再依次把三张依次放到末尾，打开上面一张，刚好是3；如此继续下去，直至打开最后一张是n。
【输入样例】
8
【输出样例】
1 7 5 2 6 8 4 3
思路分析：观察输出样例，1后面空两个未赋值的数后放入2，然后空三个未赋值的数后放入3，然后进入约瑟夫环（下标取余即可实现循环），然后空四个未赋值的数后放入4……，以此类推即可。

#include<iostream>
using namespace std;

int main() {
	int n; cin >> n; //n<1000
	int arr[1001] = { 0 };
	int pos = 0, count = 3;//pos指向放数的位置,count表示pos进入到下一个pos的步长，比如1在下标1的位置，2在下标4的位置
	for (int i = 0; i <n; i++) {
		arr[pos%n] = i+1;  //约瑟夫环的思想
		if (i == n-1) break;
		int j = 0;
		while (j!=count) {  //该循环意思为经过count个不为零的数。
			pos++;
			if (arr[pos%n] == 0) {
				j++;
			}
		}
		count++;
		
	}

	for (int i = 0; i <n; i++) {
		cout << arr[i] << "  ";
	}
	return 0;
}

持续更新中……

码农公寓