Java教程

算法刷题的基础(一)——必会的算法基础知识

本文主要是介绍算法刷题的基础(一)——必会的算法基础知识,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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,可以写成这个形式:
wumiaosu

对于一个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;
}

持续更新中……

这篇关于算法刷题的基础(一)——必会的算法基础知识的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!