入门篇-图形输出,日期问题,进制转换--《算法笔记》同步笔记总结与补充

2020-03-02

由于这三个专题比较简单，放在一起讲了

专题要点：

图形输出：

即为找规律，此类型题一定在图形排列中存在规律（行，列，空格等），如果一时没有发现，不用死磕，但光凭想象不够，多画几张简单的符合题意的图更直观一些。

日期问题：

总结下来无非是判断天数，星期，日期的问题（若是填空题，Excel即可，没必要写程序求解）。

进制转换：

总结一下基础题型，十进制与r进制相互转换，其中：十进制转r进制用除模取余法，r进制转十进制可对字符串使用for循环遍历：num = num*10+(str[i] - ‘0’)（或者str[i] - ‘A’）；r1进制转r2进制（r1,r2均非十进制）：均先转化为十进制再转化会相应进制

几点注意：

1、图形输出，尤其是字符矩阵，要注意先对矩阵进行初始化（根据题目要求初始化成相应字符，如空格等），否则在控制台（黑框框）中看不出来，但是OJ系统可以识别出来错误。
2、对于不同月份的天数，建议打表（建立散列）
3、处理月份要注意修改平闰年天数
4、处理星期要注意天数加和对7取模，星期的表要从下标0开始
5、进制转换，当涉及到十进制以上的进制输出时，需要用字符表示，可以打表或者 写switch或者 字符串+常数转换（强烈建议打表！）
6、进制转换的循环使用do-while较合适，可以考虑输入的num = 0的问题，若使用while则需要特判0
7、对类似时分秒单位的转换处理，可以先转换为最小计量单位，如秒，经过运算之后统一转换为时分秒。
如：(ans / 3600, ans % 3600 / 60, ans % 60)，即（hh,mm,ss）

日期问题的题目类型

《算法笔记》中的相关题目很少，PAT上也不多，难道是因为觉得太水了？其实日期问题有很多细节值得仔细推敲处理

日期打表

int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};//日期打表，从下标1开始
bool leapyear(int y)//平闰年判断
{
	if(y % 4 == 0 && y % 100 != 0)
	{
		month[2] = 29;//在子函数中直接修改2月的天数
		return true;
	}
	else if(y % 400 == 0)
	{
		month[2] = 29;
		return true;
	}
	else
	{
		month[2] = 28;
		return false;
	}
}

星期问题-判断每个月的dd日是星期几

已知1900年1月13日是星期五，求从1900年1月13日到2019年12月13日，有多少个月的13日是星期三，输出个数

#include <bits/stdc++.h>
using namespace std;
int monthday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string week[7] = {"Mon", "Tue", "Wen", "Thur", "Fri", "Sat", "Sun"};
bool leapyear(int y)
{
	if(y % 4 == 0 && y % 100 != 0)
	{
		return true;
	}
	else if(y % 400 == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main(int argc, char *argv[]) {
	int ans = 5;//1900/1/13
	int cnt = 0;
	for(int i = 1900; i <= 2019; i++)
	{
		if(leapyear(i))
		{
			monthday[2] = 29;
		}
		else
		{
			monthday[2] = 28;
		}
		for(int j = 1; j <= 12; j++)
		{
			//ans = (ans + monthday[j]) % 7;
			ans += monthday[j] % 7;
			ans %= 7;
			if(ans == 2)
			{
				cnt++;
			}
		}
	}
	cout<< cnt << endl;
	return 0;
}

星期问题-输入日期，输出星期

从1年开始作循环，直到输入的日期为止，统计所有天数，在对7取模

#include <bits/stdc++.h>
using namespace std;
int monthday[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//由于取模的原因，要从下标0开始，因为不会有对7取模后还为7的
string week[7] = {"Mon", "Tue", "Wen", "Thur", "Fri", "Sat", "Sun"};
bool leapyear(int y)
{
	if(y % 4 == 0 && y % 100 != 0)
	{
		return true;
	}
	else if(y % 400 == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main(int argc, char *argv[]) {
	int year, month, day;
	scanf("%d %d %d", &year, &month, &day);
	int ans = 0;
	for(int i = 1; i < year; i++)
	{
		if(leapyear(i))
		{
			ans += 366 % 7;
			ans %= 7;
		}
		else
		{
			ans += 365 % 7;
			ans %= 7;
		}
	}
	if(leapyear(year))
	{
		monthday[2] = 29;
	}
	else
	{
		monthday[2] = 28;
	}
	for(int i = 1; i < month; i++)
	{
		if(monthday[i] == 31)
		{
			ans += 31 % 7;
			ans %= 7;
		}
		else if(monthday[i] == 30)
		{
			ans += 30 % 7;
			ans %= 7;
		}
		else if(i == 2)
		{
			ans += monthday[2] % 7;
			ans %= 7;
		}
	}
	ans += (day - 1) % 7;
	ans %= 7;
	cout << week[ans] << endl; 
	return 0;
}

判断日期间的天数

#include <bits/stdc++.h>
using namespace std;
int month[13]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool leapyear(int y)
{
    if(y % 4 == 0 && y % 100 != 0)
    {
        return true;
    }
    else if(y % 400 == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    int y1, m1, d1;
    int y2, m2, d2;
    scanf("%d %d %d", &y1, &m1, &d1);
    scanf("%d %d %d", &y2, &m2, &d2);
    int ans = 0;
    while(y1 != y2 || m1 != m2 || d1 != d2)
    {
    	if(leapyear(y1)) 
    	{
    		month[2] = 29;
    	}
    	else
    	{
    		month[2] = 28;
    	}
        d1++;
        ans++;
        if(d1 > month[m1])
        {
            d1 = 1;
            m1++;
        }
        if(month[m1] == 0)
        {
            m1 = 1;
            y1++;
        }
    }
    cout << ans << endl;
}

进制转换完整版代码

方法：除基取余法
主要问题：细心！不要想当然做题！

出现的问题

PAT.A1027
原本想使用switch对十三进制进行输出和字符转换，结果弄巧成拙，忘记在switch的case中加break了（break是为了跳出switch循环，如果不加，则从满足条件的case后一直执行语句，直到走到switch结束），结果找了老半天错误，建议打表和字符+常数进行转换！！！
PAT.A1058
做各个进制的加法运算时的进位问题，一定要在加上之前的进位后，对其取余做除法

1
2
3

//carry是上一位运算后产生的进位
ans = (a + b + carry) % r;//这一位上的得数
carry = (a + b + carry) / r;//这一位相加后产生的进位

//十进制转化为任意进制
//任意进制转化为十进制
//二进制转化为十六进制
#include<bits/stdc++.h>
using namespace std;
//进制打表
char table[20] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
const int Max = 100005;
char str[Max];
string arr;
int num;
int R, r, index;//R:进制, r:余数,index:下标

void display()
{
    for(int i = index - 1; i >= 0; i--)
    {
        cout << str[i];
    }
}

void fun1(int num, int R)
{
	if(num < 0)
	{
		cout << "-";
		num = - num;
	}
    index = 0;
    while(num != 0)
    {
        r = num % R;
        num = num / R;
        if(r <= 9)
        {
            str[index++] = '0' + r;
        }
        if(r > 9)
        {
            str[index++] = 'A' + r - 10;//字符转换
        }
    }
    display();
}

int fun2(string num, int R)
{
	int len = num.length();
	int ans = 0;
	for(int i = len - 1; i >= 0; i--)
	{
		if(num[i] >= 48 && num[i] <= 57)
		{
			ans += (num[i] - '0') * pow(R, -i - 1 + len);
		}
		if(num[i] >= 65 && num[i] <= 70)
		{
			ans += (num[i] - 'A' + 10) * pow(R, -i - 1 + len);
		}
	}
	return ans;
}

int main()
{
    int opt;
    cout << "1.十进制转化为任意进制" << endl;
    cout << "2.任意进制转化为十进制" << endl;
    cout << "3.二进制转化为十六进制" << endl;
    cin >> opt;
    switch(opt)
    {
        case 1:
            {
                cout << "Get Decimal Number:";
                cin >> num;
                cout << "Set Number System:";
                cin >> R;
                fun1(num, R);
                break;
            }
        case 2:
            {
            	cout << "Get Number:";
            	cin >> arr;
            	cout << "Tell the Number Systerm of the Number:";
            	cin >> R;
            	int ans = fun2(arr, R);
            	cout << ans;
                break;
            }
        case 3:
            {
            	cout << "Get Number:";
            	cin >> arr;
            	int ans = fun2(arr, 2);
            	fun1(ans, 16);
                break;
            }
    }
}