如题：
给定一个带通配符问号的数W，问号可以代表任意一个一位数字。
再给定一个整数X，和W具有同样的长度。以此类推，就可以得出W比X大总个数
c#示例代码如下：
/// <summary>
/// 使用算法推算w大于x的个数
/// </summary>
/// <param name="string_W"></param>
/// <param name="string_X"></param>
/// <returns></returns>
private int getNum(string string_W, string string_X)
{
if (int.Parse(string_W.Replace(‘?‘, ‘9‘)) <= int.Parse(string_X))
{
return 0;
}
int firstCharIndex = -1;//第一个通配符的索引
int secondCharIndex = -1;//第二个通配符的索引
int value_x = 0;////字符串string_X中在第一个通配符相应位置的数字的值
int charCount = 0;//通配符数量
//找到第一个通配符的索引和第二个通配符的索引
for (int i = 0; i < string_W.Length; i++)
{
if (string_W[i] == ‘?‘)
{
charCount++;
if (firstCharIndex == -1)
{
value_x = int.Parse(string_X[i].ToString());
firstCharIndex = i;
continue;
}
if (firstCharIndex != -1 && secondCharIndex == -1)
{
secondCharIndex = i;
}
}
}
//第一个通配符前面有数字,并且与x不相等的情况
if (firstCharIndex > 0)
{
int formerValue_W = int.Parse(string_W.Substring(0, firstCharIndex));
int formerValue_X = int.Parse(string_X.Substring(0, firstCharIndex));
if (formerValue_W > formerValue_X)
{
//如果之前的数据W>X,则=通配符的个数n 10的n次方
return (int)Math.Pow(10, charCount);
}
else if (formerValue_W < formerValue_X)
{
return 0;
}
}
//如果第一个通配符之前的数相等或没有数字,判断通配符和X字符的大小情况
if (charCount > 1)
{
//递归计算出结果 第一个通配符大于x的情况+等于x时进行递归推算
return (9 - value_x) * (int)Math.Pow(10, charCount - 1) +
getNum(string_W.Substring(firstCharIndex + 1), string_X.Substring(firstCharIndex + 1));
}
else
{
//只有一个通配符，判断当通配符与x相同位置的整数相同时，w和x的大小
int W = int.Parse(string_W.Replace(‘?‘, string_X[firstCharIndex]));
int X = int.Parse(string_X);
if (W > X)
{
return (9 - value_x) + 1;
}
else
{
return (9 - value_x);
}
}
}
/// <summary>
/// 使用常规逻辑遍历计算w大于x的个数
/// </summary>
/// <param name="string_W"></param>
/// <param name="string_X"></param>
/// <returns></returns>
private int CalNum(string string_W, string string_X)
{
int value_x = int.Parse(string_X);
string[] parms_w = string_W.Split(‘?‘);
string[] charDic = new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "l", "m" };//最多10个
//字符字典，用于依次替换string_W中的通配符，以方便递归方法中的遍历
string_W = "";
for (int i = 0; i < parms_w.Length; i++)
{
string_W += parms_w[i] + charDic[i];
}
string_W = string_W.Substring (0,string_W .Length -1);
int charCount = parms_w.Length - 1;
return CalNum_sub(string_W, value_x, charDic, charCount); ;
}
/// <summary>
/// CalNum方法中用到的递归计算
/// </summary>
/// <param name="string_W"></param>
/// <param name="value_x"></param>
/// <param name="charDic"></param>
/// <param name="charCount"></param>
/// <returns></returns>
private int CalNum_sub(string string_W, int value_x, string[] charDic, int charCount)
{
int total = 0;
for (int k = 0; k < 10; k++)
{
string temp = string_W.Replace(charDic[charCount - 1], k.ToString());
if (charCount > 1)
{
total += CalNum_sub(temp, value_x, charDic, charCount - 1);
}
else
{
if (int.Parse(temp) > value_x)
{
total++;
}
}
}
return total;
}
/// <summary>
/// 测试方法
/// </summary>
/// <param name="string_W"></param>
/// <param name="string_X"></param>
/// <returns></returns>
private string testNum(string string_W, string string_X)
{
Stopwatch watch = new Stopwatch();
watch.Start();
int v1 = CalNum(string_W, string_X);
watch.Stop();
string t1 = watch.ElapsedTicks.ToString();
watch.Reset();
watch.Start();
int v2 = getNum(string_W, string_X);
watch.Stop();
string t2 = watch.ElapsedTicks.ToString();
return (v1 + "--" + v2 + "\r\n" + t1 + "--" + t2).ToString();
}
算法实战：给定一个带通配符问号的数W，问号可以代表任意一个一位数字。 再给定一个整数X，和W具有同样的长度。 问有多少个整数符合W的形式并且比X大？,布布扣,bubuko.com
算法实战：给定一个带通配符问号的数W，问号可以代表任意一个一位数字。 再给定一个整数X，和W具有同样的长度。 问有多少个整数符合W的形式并且比X大？
原文：http://blog.csdn.net/kevindr/article/details/24172991