数据结构与算法之倒推算法

倒推算法概念

所谓的倒推法（Inverted Recursion）是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。
在不知前提条件的情况下，经过从后向前递推，来求解问题的初始数据，即由结果倒过来推解它的前提条件。另外在对一些进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法，则问题很容易理解和解决。

回文日期

问题：
在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月 份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。
牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现 在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存 在的日期是回文的。
一个8位数字是回文的，当且仅当对于所有的i （ 1 <=i<= 8 )从左向右数的第i个 数字和第9-i个数字（即从右向左数的第i个数字）是相同的。
例如：
•对于2016年11月19日，用8位数字20161119表示，它不是回文的。
•对于2010年1月2日，用8位数字20100102表示，它是回文的。
•对于2010年10月2日，用8位数字20101002表示，它不是回文的。
每一年中都有12个月份：
其中，1、3、5、7、8、10、12月每个月有31天；4、6、9、11月每个月有30天；而对于2月，闰年时有29天，平年时有28天。
一个年份是闰年当且仅当它满足下列两种情况其中的一种：
1.这个年份是4的整数倍，但不是100的整数倍；
2.这个年份是400的整数倍。
例如：
•以下几个年份都是闰年：2000、2012、2016。
•以下几个年份是平年：1900、2011、2014。
输入输出格式
输入格式：
输入包括两行，每行包括一个8位数字。
第一行表示牛牛指定的起始日期。
第二行表示牛牛指定的终止日期。
保证date_i和都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0。
保证date1 —定不晚于date2。
输出格式：
输出一行，包含一个整数，表示在date1和date2之间，有多少个日期是回文的。
输入输出样例
输入样例#1：
20110101
20111231
输出样例#1：
1
输入样例#2：
20000101
20101231
输出样例#2：
2
说明
【样例说明】
对于样例1，符合条件的日期是20111102。
对于样例2，符合条件的日期是20011002和20100102。
【子任务】
对于60%的数据，满足date1 = date2。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool panduan(int n)
{
	int year=n/10000;
	int month=n%10000/100;
	int day=n%100;
	int a[12]={31,28,31,30,31,30,31,31,30,31,30,31};
	if((year%400)||(year%4==0 && year%100!=0))
		a[1]++;
	if(month<1||month>13) //月份不合法 
		return false;
	if(day<1||day>a[month-1])//日期不合法 
	 return false;
	return true;//合法返回true 
}
int main()
{
	int start,end,i,j,k;
	cin>>start>>end;// 开始和结速时间 
	for(i=start;i<=end;i++)
	{
		j=i%10*10+i%100/10;
		k=i%1000/100*10+i%10000/1000;
		if(i/10000!=(j*100+k)) continue ;// 不是回文继续 
	  	if(panduan(i))//判断年份是否合法 
	  	 		 cout<<i<<endl;
	}
	return 0;
}

求数字

问题：
有这样的五位数n，满足如下条件：
n是回文数
n是个完全平方数
n的个位数字之和k，也是完全平方数。
k是两位数，k的两位数之和为r，也是完全平方数
分析：
采用倒推法，从第四步入手。
r是个完全平方数且是一位数，只能为1、4、9三个数字之一。
k是两位数且为完全平方数，只能是16、25、36三个之一（因五位数数字之后不能超过45）。
由前面两点可推出，五位数数字之和只能等于36。
n是回文数，可以表示为n=abcba的形式。先分析a的取值为1～9：
a不能为1、2、3、4，因36-a2>27，其它三个数字之和不能超过27。
a不能为5，若为5，则b必为2，那么c=36-（5+2）2=12。
a不能为7、8。因为没有一个完全平方数的末位数为7和8。
a只能为6或9。
a为6时：有69696 和68886（因68886%4=2不是完全平方数）
a等于9时：有99099、98289、97479、96669、95859
99099、97479、95859这三个数除以4，不能整除或余数不为1，不是完全平方数。
98289和96669，末尾是9，只能是307、313的完全平方数。因313313=97969 ，307307=94249 因此这两个数不是完全平方数
综上所述，该数应该是69696
代码：

#include <cstdio.h>
using namespace std;
int main()
{
  int i,n,a,b,c,d,e;
  for(i=100;i<320;i++)
   {
n=i*i;
a=n/10000;
e=n%10;
b=n%10000/1000;
c=n%100/10;
d=n%1000/100;
if(a==e&&b=d&&(a+b+c+d+e==36))
  printf(“ %d\n”,n);
   }
   return 0；
}

迭代法

概念：迭代法（iteration）也叫“辗转法”，是一种不断用变量旧值推出新值的解决问题的方法。

步骤

1.确定迭代模型
根据问题描述，分析出前一个值与下一个值的迭代关系数学模型。
2.建立迭代关系式
递推数学模型一般是带下标的字母，在算法设计中要将其转换为“循环不变式”（迭代关系式）
3.对迭代过程进行控制
确定在什么时候结束迭代过程。

迭代模型是通过小规模问题逐步解决大规模问题的解。

1.递推法（正推）

问题：兔子繁殖问题（斐波拉契数列）
一对兔子从出生后第三个月开始，每月生一对兔子。小兔子到第三个月又开始生下一代兔子。假如兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少对兔子？
解决：
首先把情况列举出来，发现其中的规律，找到一个不变式（即循环不变式）
表格中是兔子的对数（不是只数）

说明：第一个月和第二个月都是一对兔子，因为兔子还没成熟（三个月成熟）。
第三个月生了一对小兔子，现在兔子总对数是两对。（1+1=2）
第四个月第一对兔子又生了一对（成熟兔子每个月都生一对），现在兔子总对数是3对。（2+1=3）
第五个月，两对成熟兔子生了两对，现在兔子总对数是5对。（3+2=5）
第六个月，三对成熟兔子生了三对，现在兔子总数是8对。（5+3=8）
…
以此类推，我们发现兔子数量符合以下规律：

//用三个变量实现数量的累加
c=a+b;
b=a;
a=c;

完整代码如下：

#include<iostream>
using namespace std;
int main(){
	int i;
	int a=1,b=1,c;//a，b代表第一个二月的兔子数量
	//计算十二个月的兔子数量 
	for(i=0;i<12;i++){
		c=a+b;
		cout<<"第"<<i+1<<"个月兔子数量:"<<c<<endl;
		b=a;
		a=c;
	}
	return 0;
}

运行结果:

2.倒推法

概念：
从后向前推解问题，即由结果倒过来推解前提条件。
问题：猴子吃桃问题
一只小猴子摘了若干桃子，每天吃现有桃子的若干个多一个，到第10天时就只有一个桃子了，求原有多少个桃？
解决：

递推公式为(此处i和i-1为下标):
ai=(1+ai-1)*2 i=9,8,7,6,…,1
完整代码如下:

#include<iostream>
using namespace std;
int main(){
	int i,a;
	a=1;
	for(i=9;i>=1;i--){
		a=(a+1)*2;
	}
	cout<<"原有桃子数为:"<<a<<endl;
	return 0;
} 

运行结果:

最后

原创不易，如果对您有帮助，请点个赞再走呀（づ￣3￣）づ╭❤ ～拜托啦

写在前面的话——

这次主要是就是开始讲算法了，主要的来说，主要是分治法、贪婪法还有动态规划，这些我觉得是一种处理问题的思想，还有什么蛮力法，倒推法什么的，也算是思想，但是更多的，这个也算是一种工具，会比较常见的用在之前的三种方法中，特别是倒推，其实我也觉得倒推并没有多神奇，毕竟我们做数学题的时候，就是很多时候按照正常的顺序思考不出来，反着推就能比较顺利，而且我觉得这些个算法，只能算是训练，而实际应用的时候，应该还是适可而止，不要过分强求，实际问题一般都比这些训练题复杂得多，所以我始终觉得这个只是锻炼一个思想而已！

第二篇——

我觉得下面三个题比较简单，就是第一个题有点难度，不过因为是书上例题，所以并没有花很多功夫去思考，反过来想的话，这个题也没法想的太细，因为需要很多数学思想的支撑，特别是一开始要建立一个数学模型，所以掌握方法领悟技巧就好，至于为什么要这么算，凭什么这么算就是最节约的，不讨论比较好。

1.穿越沙漠问题

一辆吉普车穿越1000千米的沙漠。吉普车的总装油量为500加仑，耗油量为1加仑/千米。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。若吉普车用最少的耗油量穿越沙漠，应在那些地方建立油库，以及各处存储的油量。

算法设计：

这个题由于要求用最少的耗油量，也就是最后穿越沙漠之后刚好油量为0，同时，很明显，直接开是无法穿越的，在中间架设油库，只能使用这辆车，一次最所携带500加仑并且行进返回都需要耗油，如果正向分析问题会非常复杂无从下手，但是倒推会发现还是有迹可寻。

从终点倒推，刚好油量为0，则在离终点500千米的地方A建立一个油库并且存油500加仑，设A点之后的油库在B点，从B点到A点运油，满足条件的最佳方案是B点到A点共走三次，第一、二次来回耗油量为装载量的2/3，储油量为装载量的1/3，第三次单向行驶耗油量为装载量的1/3，储油量为装载量的2/3。统计一下，B点的储油量为1000加仑，此段长度为500/3千米。

同理分析B点之后的油库C点，应该需要往返5次，位置就在距离B点500/5千米的位置，存油量为1500，以此类推

代码如下：

#include <stdio.h>
 
int main()
{
       int dis[100],k,oil[100];
       dis[1]= 500;
       k= 1;
       oil[1]= 500;
       do {
              k++;
              dis[k]= dis[k-1] + 500/(2 * k - 1);
              oil[k]= 500 * k;
       }while(dis[k] < 1000);
 
       oil[k]= 500 * (k - 1) + (1000 - dis[k]) * (2 * k - 1);
       dis[k]= 1000;
 
       int i = 0;
       for(;i<k;i++) {
              printf("第%d个临时油库在距离起点%d的位置，储油量为%d\n",i+1,1000-dis[k-i],oil[k-i]);
       }
 
       return 0;
}

算法分析：通过倒推法可以解决一些正向推导很难处理的问题，非常有效。

2.54张扑克牌，两个人轮流拿牌，每个人每次最少取1张，最多取4张，谁拿最后一张谁输。编写模拟计算机先拿牌且必胜的算法。

算法设计：

根据题意，必须先拿且必胜，则可以理解为，在54张减去第一次拿的牌数后，每轮对方先拿，自己后拿，直到最后一轮，刚好剩下1张牌，且对方的拿牌数为一个1-4的随机数，那么此时应该考虑，对方每次的拿牌数是不能确定的，但是每轮的拿牌数是可以确定的，就是可以在对方拿完之后，自己拿一定数量的牌凑成一个可以一定达成的数字，这个数字很明显应该是5，即每轮拿5张牌，最后还剩一张，且之前减去了已经拿走的牌，则很明显，先拿走3张之后，还剩51张，每轮拿走5张，十轮之后，还剩一张，此时必定获胜。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int main()
{
       int i = 3;//计算机初始拿的牌数
       int n = 54;//当先的牌数量
       int i_times = 1;//总计拿了多少次
       int p;//另一方的拿牌数，在1-4之间随机生成一个数
       srand(time(0));
       while(n > 0)
       {
              p= rand()%4 + 1;
              printf("the%d time computer select %d paper and you %d paper\n",i_times,i,p);
              n-= i+p;
              printf("nowthe paper has left %d\n",n);
              i_times++;
              i= 5 - p;//需要在对方拿牌之后，再取的牌数和之前的牌数凑成固定的5张
              if(n - i == 1) {//如果还剩一张，此时不可以继续随机了，只能拿这张牌
                     printf("the%d time computer select %d paper and you have the last one\n",i_times,i);
                     break;
              }
       }
       return 0;
}

算法分析：这个算法的关键在于如何保证最后一定剩一张牌给另一方，而且要保证每一轮拿牌保证一样的数量才可以进行控制，但是每一轮先拿牌的话，就无法控制，只能再对方先拿牌之后才能根据他的数量再决定该拿多少张，此时根据规则，必须先拿又必须赢，此时需要考虑先拿多少张，然后开始每一轮拿牌，最后剩一张牌，顺利写出代码

3.有一堆棋子，2枚2枚的数，最后余1枚；3枚3枚的数，最后余2枚；5枚5枚的数，最后余4枚；6枚6枚的数，最后余5枚；7枚7枚的数，最后正好数完。变成求出这堆棋子最少有多少枚棋子。

算法设计：

从题目来看，很明显是求一个数，这个数对2求余得1，对3求余得2，对5求余得4，对6求余得5，对7整除，使用蛮力法，从最小的数7开始累加，直到满足条件结束

代码如下：

int main()
{
 
       int i = 7;
       while(1) {
              if(5 == i % 6 && 4 == i% 5 && 2 == i % 3 &&1 == i % 2) {
                     printf("这堆棋子的数量为%d\n",i);
                     break;
              }else
                     i+= 7;
       }
 
       return 0;
}

算法分析：以上实际采用枚举法，将每一个数都进行运算求得余数进行比对，直到符合所有条件的数出现为止，这里简单设计了下，不用每个数都判断，只需要判断7的倍数即可，可以减少循环次数，整个算法看起来比较清晰简洁。