11/27
《程序设计方法(C\C++)》是北京理工大学的一门课程,该课通过北京理工大学网络教室评测的编程练习题计算平时成绩。

21 合并字符串

核心思想:依次将两个字符串存储到数组中,并利用归并排序思想进行输出。也就是每次比较两个字符串中最靠前还没有被输出的字符,输出最小/大的,然后将对应字符串指向还没有输出字符的标记变量向后移动,一直到两个字符串都输出完为止。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main() {
	char str[2][256];
	int i,j;
	gets(str[0]);
	gets(str[1]);
	i=0;
	j=0;
	while (i<strlen(str[0])
		   || j<strlen(str[1])) {
		if (i==strlen(str[0])) {
			putchar(str[1][j++]);
			continue;
		}
		if (j==strlen(str[1])) {
			putchar(str[0][i++]);
			continue;
		}
		if (str[0][i]<str[1][j])
			putchar(str[0][i++]);
		else
			putchar(str[1][j++]);
	}
	if (strlen(str[0])+strlen(str[1]))
		printf("\n");
	return 0;
}

22 串的减法

核心思想:对于被减的字符串s[],依次从头到尾遍历各个字符s[i],对于遍历到的每一个字符都在减数字符串t[]中寻找是否出现,如果没有出现则将s[i]输出出来。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
	char s[256],t[256];
	int i,j,k;
	gets(s);
	gets(t);
	for (i=0;i<strlen(s);i++) {
		for (j=0;j<strlen(t);j++)
			if (s[i]==t[j])
				break;
		if (j==strlen(t))
			putchar(s[i]);
	}
	printf("\n");
	return 0;
}

23 整数问题

有若干同学要看我的2行程序代码,我就把它贴了出来。其实这道题我当初做的时候用的也是最容易想到的枚举数字的想法,结果在n=8的时候就成功的超时了,可是该点在本地运行大约2秒就可以跑出解,再加上这道题数据量不大、我又不想重新写正经的算法了,于是就将所有的结果算出来,存入了程序中。既然是乱搞出来的程序,就干脆乱搞到底算了,于是我就把所有的回车都删掉了……大家不要学我。

#include <stdio.h>
int main() {int i,j,k,n,start,end,ret;int form[9]={0,9,22,24,16,7,7,1,0};scanf("%d",&n);ret=form[n];printf("%d\n",ret);return 0;}

这个是正经的程序。

核心思想:由于每前i位,都被要求能被\(i^2\)整除。而对n=k时的结果来说,前k-1位数字一定包含了当n=k-1时的结果们(该词语出《高等代数》课程上的“坐标们”),因此就可以由小的位数不断的推到高的位数。

下面的程序中,使用了递归的手段来实现上述递推的过程,其中theNumber是对于len位的数字的一个可以成为解的数,值得注意的是,这个数字在被传入函数了以后才被判断是否是可行的。当其可行的时候,再枚举下一位。len位的这个具体数字对应的解的个数,就是其枚举的各种下一位的解的个数和,也就是\(ret(theNumber)=\sum_{i=0}^9{ret(10theNumber+i)}\).

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int calSum(int theNumber,int len,int n) {
    if (len&&theNumber%(len*len))
        return 0;
    if (len==n)
        return 1;
    int ret,i;
    ret=0;
    for (i=0;i<=9;i++)
        if (len||i)
            ret+=calSum(theNumber*10+i,len+1,n);
    return ret;
}

int main() {
	int i,j,k,n,start,end,ret;
	scanf("%d",&n);
    printf("%d\n",calSum(0,0,n));
    return 0;
}

24 科学记数法

核心思想:_strtol(char* str)函数是用来将传入的字符串的每一个字符转化为整型数字的函数,由于系统函数不是标准函数,在GCC评测环境下无法运行,所以自己写了一个。

程序的想法类似于我们学过的浮点数,利用_strtol()将前面的有效位数存入数组val[]中,将指数转入ex[]中,同时还将小数点位置存入了end变量中,之后将ex[]转换整型数字,然后与end做运算,算出结果的小数点位置。最后据此补零、加小数点并输出val[]内的数字。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int _strtol(char* str) {
	int i,j=0;
	for (i=0;i<strlen(str);i++)
		if (str[i]>='0'&&str[i]<='9')
			j=j*10+(str[i]-'0');
	if (str[0]=='-')
		j=-j;
	return j;
}

int main() {
    int i,j,k,n;
    int flag=0;
    char theNumber[256],val[256],ex[256];
    int start=0,end=-1;
    double a;
    gets(theNumber);
    j=0;
    k=0;
    for (i=0;i<=strlen(theNumber);i++)
        switch (theNumber[i]) {
        	case '.':
				end=j;
				break;
			case 'E':
			case 'e':
				flag=1;
			case ' ':
				break;
			default:
				if (flag)
					ex[k++]=theNumber[i];
				else
					val[j++]=theNumber[i];
				break;
		}
	if (end==-1)
		end=j;
	ex[k]='\0';
	n=_strtol(ex);
	end+=n;
	start+=n;
	if (start>0)
		start=0;
	for (i=start;i<end+8;i++) {
		if (i==end)
			printf(".");
		if (i<j&&i>=0)
			printf("%c",val[i]);
		else
			printf("%d",0);
	}
	printf("\n");
    return 0;
}