学步园

1、编程计算从 1 到 2008080808 之间的整数有多少个含有数字7。

2、结构RECT可以表示一个平面上的矩形区域： struct RECT {   int left, right, top, bottom; }; 编程计算两个矩形区域A和B构成的区域总面积。

3、将给定的字符串以词为单位倒序，同时给定一个子串，若字符串中有部分内容与子串相同则该部分不倒序。 例：给定字符串“The quick brown fox jumps over the lazy dog”和子串“brown fox”， 倒序结果是“dog lazy the over jumps brown fox quick The”

目前只有1，2题，第三题会尽快跟上

第一题：

//1-2008080808之间有多少个数字含有7
#include <iostream>
#include <cmath>
using namespace std;

//计算[1, 10^n]之间有多少个数字含有7 
int Seven(int n) {
	if(n == 1)
		return 1;
	return int(9 * Seven(n - 1) + pow(10.0, n - 1));
}

//输入：数字n
//输出：[1, n]之间有多少个数字含有7 
int search_seven(int n) {
	//如果n<10那么就直接判断 
	if (0 <= n && n < 7)
		return 0;
	if (7 <= n && n < 10)
		return 1;
	int m = (int)log10(n);	//n是10^m级别的数字 
				//比如，n=200，m=2，n是10^2级别的数字 

	int q;	//商
	int r;	//余数

	q = n / int(pow(10.0, m));
	r = n % int(pow(10.0, m));

	if (q < 8)
		return Seven(m) * q + search_seven(r);
	if (q == 8)
		return Seven(m) * 7 + int(pow(10.0, m)) + search_seven(r);
	if (q == 9)
		return Seven(m) * 8 + int(pow(10.0, m)) + search_seven(r);
}

int main() {
	int result;
	result = search_seven(2008080808);
	cout << result;
	cin.get();
} 
//结果 1,229,473,242

/*
1、编程计算从 1 到 2008080808 之间的整数有多少个含有数字7。 
为了方便，用S(n)来表示[1,10^n]区间内有多少个7
S(1)=1
S(2)=9×S(1)+10^(2-1)
S(3)=9×S(2)+10^(3-1)
S(4)=9×S(3)+10^(4-1)
...
S(n)=9×S(n-1)+10^(n-1)

S(1)=1
S(2)=19
S(3)=271
S(4)=3439
S(5)=40951
S(6)=468559
S(7)=5217031
S(8)=56953279
S(9)=612579511

是这样的
[1,10)有一个7
[1,10^2)由10个类似于[1,10)的区间组成，应该是有10×S(1)个7，但是因为[1,100)区间里有一个[70,80)
所以，S(2)=9×S(1)+10

再看[1,10^3)，由10个类似于[1,100)的区间组成，应该是有10×S(2)个7，但是因为[1,1000)区间里有一个[700,800)
所以，S(3)=9×S(2)+100

于是就推出了这样的公式，S(n)=S(n)=9×S(n-1)+10^(n-1)

那么2,008,080,808这个数字可以拆分成为
 1,000,000,000×2 + 8,000,000 + 80,000 + 800 + 8
=1,000,000,000×2 + (10,000,000-2,000,000) + (100,000-20,000) + (1,000-200) + 8
实际上就是求这几个部分各自有多少个含有7的数字，然后相加。

结果是 1,229,473,242
*/

第二题:

//2、结构RECT可以表示一个平面上的矩形区域： 
//struct RECT {   int left, right, top, bottom; }; 
//编程计算两个矩形区域A和B构成的区域总面积。
#include <iostream>
#include <cmath>
using namespace std;

struct RECT {
	int left;
	int right;
	int top;
	int bottom; 
};

//计算面积的
int area(RECT& r) {
	return abs((r.right - r.left) * (r.bottom - r.top));
}

//本题采用的是初中数学里面用到的平面直角坐标系
double sum_area(RECT r1, RECT r2) {
	//首先计算面积，大小交换 
	//保证r1大，r2小 
	if (area(r1) < area(r2)) {
		RECT t = r1;
		r1 = r2;
		r2 = t;
	}

	//两个矩形是否有共同区域（不仅仅是相交，包括大矩形包含小矩形的情况）
	//首先看(r1.top - r1.bottom)/2 + (r2.top - r2.bottom)/2 >
	//		|(r1.top + r1.bottom)/2 - (r2.top + r2.bottom)/2|
	//并且 (r1.left - r1.right)/2 + (r2.left - r2.right)/2 >
	//	    |(r1.left + r1.right)/2 - (r2.left + r2.right)/2| 

	//即两个矩形1/2高的和的是否超过它们中心点的垂直间距，并且 
	//1/2长的和是否超过它们中心点的水平间距 

	/*	计算两矩形共同部分所构成的矩形C的长和高
		 C的长 = 两矩形1/2长的和 - 中心点水平间距
		 C的高 = 两矩形1/2高的和 - 中心点垂直间距

		如果C的长>=较小矩形的长，那么较小矩形的长被完全包含在较大矩形里面
	计算C的面积时采用较小矩形的长 

		如果C的高>=较小矩形的高，那么较小矩形的高被完全包含在较大矩形里面 
	计算C的面积时采用较小矩形的高

		如果以上两个条件同时满足，那么较小矩形就被完全包含在较大矩形内部 
	*/

	double vCentralDist = //中心点垂直间距
		fabs(double((r1.top + r1.bottom))/2 - double((r2.top + r2.bottom))/2);	 
	double hCentralDist = //中心点水平间距
		fabs(double((r1.left + r1.right))/2 - double((r2.left + r2.right))/2); 	
	double sum_HalfHeight = //1/2高的和
		double((r1.top - r1.bottom))/2 + double((r2.top - r2.bottom))/2;
	double sum_HalfWidth = //1/2长的和
		double((r1.right - r1.left))/2 + double((r2.right - r2.left))/2;		 

	//两矩形公共区域构成的C的长和高
	double cWidth = sum_HalfWidth - hCentralDist;
	double cHeight = sum_HalfHeight - vCentralDist;
	//如果r1完全包含r2的情况 
	if ((cWidth >= r2.right - r2.left) && (cHeight >= r2.top - r2.bottom))
		return area(r1);
	//如果r1只包含了r2的长的情况 
	else if ((cWidth >= r2.right - r2.left) && cHeight > 0) 
		return area(r1) + area(r2) - (r2.right - r2.left) * cHeight;
	//如果r1只包含了r2的高的情况 
	else if ((cHeight >= r2.top - r2.bottom) && cWidth > 0)
		return area(r1) + area(r2) - (r2.top - r2.bottom) * cWidth;
	//如果r1，r1只是相交 
	else if (cHeight > 0 && cWidth > 0)
		return area(r1) + area(r2) - cHeight * cWidth;
	//如果r1，r2完全不相交 
	else
		return area(r1) + area(r2);
}

int main() {
	RECT r1 = {4, 7, 2, 1};
	RECT r2 = {2, 5, 2, 1};
	cout << sum_area(r1, r2);
	cin.get();
}