Problem Description
A wild number is a string containing digits and question marks (like 36?1?8). A number X matches a wild number W if they have the same length, and every non-question mark character in X is equal to the character in the same position in W (it means that you can replace a question mark with any digit). For example, 365198 matches the wild number 36?1?8, but 360199, 361028, or 36128 does not. Write a program that reads a wild number W and a number X from input, both of length n, and determines the number of n-digit numbers that match W and are greater than X.
Input
There are multiple test cases in the input. Each test case consists of two lines of the same length. The first line contains a wild number W, and the second line contains an integer number X. The length of input lines is between 1 and 10 characters. The last line of input contains a single character #.
Output
For each test case, write a single line containing the number of n-digit numbers matching W and greater than X (n is the length of W and X).
Sample Input
36?1?8
236428
8?3
910
?
5
#
Sample Output
100
0
4
人在大一，刚学程设（好难...），很菜，轻喷。
上课讲到了递归法，感觉递归法比较适合这道题目，大致思路如下：
设：w中问号的个数为N；对w和x的首位数字a,b进行比较，若
任意数字均可，所以可能的情形一共有10的N次方；
任意数字均不可，所以可能的情形一共有0；
没有比较的必要，比下一位；
若a>b,是为比b大的（9-b）个数字，则是（1）；
若a=b，则是（3）；
若a<b，则是（2）；
综上，可能的情形有 （9-b）*10的N次方（实质是a>b）+下一位的可能性（实质是a=b）+0（实质是a<b）
#include <stdio.h>
#include <math.h>
int bijiao(char x[11],int w[11],int i)
{
int result=0;
int cishu=0;
int j;
int answer[11]= {0};
if(x[i]==0)
return 0; //隔断条件
else
{
for(j=i; ((x[j]=='?')||((x[j]>=48)&&(x[j]<=57))); j++)
{
if(x[j]=='?')
{
cishu=cishu+1;
answer[j]=1; //算一下x里有几个问号
}
}
if(x[i]=='?')
{
result=(9-w[i])*pow(10,cishu-1); //‘？’的时候用递归计算
result=result+bijiao(x,w,i+1);
return result;
}
else if(x[i]-48<w[i]) //之后没有数字比w大，返回0
return 0;
else if(x[i]-48>w[i]) //之后的任意数字都比w大
{
result=pow(10,cishu);
return result;
}
else if(x[i]-48==w[i]) //没啥可比的，比下一位
return bijiao(x,w,i+1);
}
}
int main()
{
char x[11]= {'a'};
char useless[11]={'a'};
int w[11]= {0};
int answer[100]= {0};
int k=0;
int sum;
while(1)
{
sum=0;
gets(x);
if(x[0]=='#') break;
//用gets直接拿，下面再换成int，方便一点
gets(useless);
for(int i=0;((useless[i]>=48)&&(useless[i]<=57));i++)
w[i]=useless[i]-48;
sum=bijiao(x,w,0);
//做一个数组把答案存起来
answer[k]=sum;
k=k+1;
}
//输出答案
for(int i=0; i<=k-1; i++)
{
if(i==k-1)
printf("%d",answer[i]);
else
printf("%d\n",answer[i]);
}
return 0;
}