程序设计编程练习题解题报告(第8周)

这次的程序里面用了一下C++的语法，如果同学看不太懂请只看核心思想即可，发的有点晚了，不好意思。

25 求最大公约数——递归

核心思想：即辗转相除法，利用每次互相取余数的方法保证方程一直是同余下等价的，具体的证明请参阅辗转相除法正确性的证明。

#include <stdio.h>
#include <iostream>
using namespace std;

template <class Tp>
	Tp gcd(Tp a,Tp b) {
		if (a<b)
			swap(a,b);
		if (!b)
			return a;
		a=a%b;
		return gcd(a,b);
	}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%d\n",gcd(n,m));
    //system("pause");
    return 0;
}

26 回文字符串——递归

核心思想：这个其实跟用循环一样，只是不断的把对一个字符串判断是否回文化归为判断其删去首尾是否回文的子问题。

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

bool isPalindrome(char *__str,int __i) {
	if (__i>=(strlen(__str)>>1))
		return true;
	if (__str[__i]==__str[strlen(__str)-__i-1])
		return isPalindrome(__str,__i+1);
	else
		return false;
}
int main() {
	char theStr[256];
	int i;
	gets(theStr);
	//printf("%d\n",strlen(theStr));
	if (isPalindrome(theStr,0))
		printf("Yes\n");
	else
		printf("No\n");
	//system("pause");
	return 0;
}

27 求序列之和——递归

核心思想：其实就是拿递归当循环用，没有什么新的，需要避免的就是递归结束的逻辑，不要弄成无限递归了。

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

int n;

float cal(int __i) {
	if (__i>n)
		return 0;
	float __ret=(float)1/__i;
	if (__i&1)
		__ret=-__ret;
	if (__i==1)
		__ret=-__ret;
	return cal(__i+1)+__ret;
}

int main() {
	float ret;
	scanf("%d",&n);
	if (n==1)
		printf("%d\n",1);
	else
		printf("%.6f\n",cal(1));
	//system("pause");
	return 0;
}

28 子串反向——递归

核心思想：这道题放了一个小小的烟幕，其实程序要过还是得写main()函数的。程序跟第26题一样，将问题不断化归成为子问题。

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

template <class Tp>
	void swap(Tp& __a,Tp& __b) {
		Tp t;
		t=__a;
		__a=__b;
		__b=t;
	}
void reverse(char str[], int start, int end) {
	if (start>=end) {
		puts(str);
		return;
	}
	swap(str[start],str[end]);
	reverse(str,start+1,end-1);
}
int main() {
	char str[50];
	int a,b;
	gets(str);
	scanf("%d %d",&a,&b);
	reverse(str,a,b);
	//system("pause");
	return 0;
}