查看完整版本: 两问题想问一下

两问题想问一下

最好最快的方法
计算从1到2008080808之间的整数有多少个含有数字7

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

怎么写

我想要 1到2008080808之间的整数有多少个含有数字7

如7，107，77，175，176，17。。。。。。。。。。。。。。

这是金山的考试题

1、1个7-2个7+3个7-4个7+5个7-6个7+7个7-8个7+9个7
2、不需要用到正则表达式么？

讨厌的算法有问题哦.....但是可以参考......

2008080808这个数不是也太大了点！

这个是从0到100的，1008080808太大了...

[code]var N:int =100;
var L:int;//数的位数；
var firstNumber:int;//数的第一个数字
var total:int;
for (var i:int = 0; i < N; i++) {
check7(i);
function check7(n:int) {
  L = Math.floor(Math.log(n)/Math.LN10);//计算该数有多少位（十进制）
  firstNumber = Math.floor(n/Math.pow(10,L));//求出第一位的数字
  if (firstNumber == 7) {//如果这个数字是7，满足条件，计数加1;
   total++;
   trace(i);
   return;
  } else if (L>0) {如果这个数字不是7，如果它是2位及2位以上的数，将首数字去掉，重复上述操作;
   n = n - firstNumber*Math.pow(10,L);
   check7(n);
  } else {如果这个数是一位数了，中止.
   return;
  }
}
}
trace("total=",total);[/code]

[[i] 本帖最后由 Poshidon 于 2008-6-18 15:17 编辑 [/i]]

var vTotal:int = 0;
for(var i:int = 0; i < 8080808; i++)
{
        if(i.toString().indexOf("7") != -1)
        {
                vTotal++;
        }
}
       
        trace(vTotal);

每次看完别人写的东西，我的第一个反应总是——我为什么就没有想到呢...:'(

import flash.utils.*;

var vTotal:int = 0;
var i = 0;
var vMax = 10000;
var vMaxNum = 80808;
function count()
{
        for(i;i < vMax; i++)
        {
                if(i.toString().indexOf("7") != -1)
                {
                        vTotal++;
                }
        }
        setTimeout(reStart, 1);
}


function reStart()
{
        if(i >= vMaxNum)
        {
                trace(vTotal);
        }
        else
        {
                vMax+= 10000;
                if(vMax > vMaxNum)
                        vMax = vMaxNum;
                count();       
        }
}

count();       
       
数太大了，慢慢等吧

[[i] 本帖最后由 wyang 于 2008-6-18 17:31 编辑 [/i]]

思维定势.....

flash貌似超过15秒就没有响应了

我最先想到的也是 wyang 的这种方法，但我想，我上面的思路没有错吧？
难道还有漏掉的？

是啊...超过15秒就出错了...

就这个题目而言，可以通过找规律来进行计算，不然数字这么大怎么运算得动......

我找的规律 :
//===================
首位数字小于7  
10==>1
100==>1*10+1 * 9^1=19
1000==>19*10+1 * 9^2=271
10000==>271*10+1 * 9^3=3439
....
20==>2
200==>2*10+2*9^1=38
2000==>38*10+2*9^2=542
20000==>542*10+2*9^3=6878
....
//======================
首位数字大于7

80==>10+7*9^0=17
800==>17*10+7*9^1=233
8000==>233*10+7*9^2=2897
80000==>2897*10+7*9^3=34073
....
90==>10+8*9^0=18
900==>18*10+8*9^1=252
9000==>252*10+8*9^2=3168
90000==>3168*10+8*9^3=37512
....

//PS:其中首位数字为7的规律我还没找出...还好这里给的数字2008080808里没有“7”,哈，先略过（把这数字的先解决再说）,找出7的话能做出个通用式求任意的了~

通过以上规律得两方法：[code]/**
* @function downFunc  //---- 7以下的计算  类似 10,100,1000,10000的计算
* @param m:uint //---- 首位数字
* @param n:uint //---- 跟随的零的个数
*/
function downFunc(m:uint,n:uint):uint {
        if (n==1) {
                return m;
        }
        return downFunc(m,n - 1) * 10 + m * Math.pow(9,n - 1);
}
/**
* @function upFunc  //---- 7以上的计算  类似 80，800，8000的计算
* @param m:uint //---- 首位数字
* @param n:uint //---- 跟随的零的个数
*/
function upFunc(m:uint,n:uint):uint{
        if (n==1) {
                return (m + 9);
        }
        return upFunc(m,n - 1) * 10 + (m - 1) * Math.pow(9,n - 1);
}

//然后最后取结果就是这样的：
var n:uint=2008080808;
function getNum(n:uint):uint {
        var tempArr:Array=String(n).split("");
        trace(tempArr);
        var result:uint=0;
        while (tempArr.length) {
                var m:uint=uint(tempArr.shift());
                if (m==0) {
                        continue;
                }
                if (tempArr.length==0) {
                        if (m>7) {
                                result++;
                        }
                        continue;
                }
                result+=m<7?downFunc(m,tempArr.length):upFunc(m,tempArr.length)
        }
        return result;
}
trace(n,"中有","<",getNum(n),">","个7");[/code]//就是把数字先拆开，比如求8888就相当于是求（8000+800+80+8）来得到结果！
//我这里计算的结果是1229473242个，由于给的数字中没有7(7的规律还没找到),这样的结果应该是对的，哈~


//大家可以测试300000,800000这样的数字

trace(downFunc(3,5))//测试300000的结果
trace(upFunc(8,5))//测试800000的结果



......终极兄弟的结果一看也应该是错了，未免太小了点~




//第二个字符串排列的问题相对比较简单：[code]var str:String="The quick brown fox jumps over the lazy dog";
var p:String="brown fox";
function reRank(str:String,p:String) {
var a:Array=str.split(p);
return a[1].split(" ").reverse().join(" ") + p + a[0].split(" ").reverse().join(" ");
}
trace(reRank(str,p));[/code]

[[i] 本帖最后由 ycccc8202 于 2008-6-19 13:45 编辑 [/i]]

:lol 看完大虾的分析
我上面的计算方法确实是错的，而且是很错:L

[[i] 本帖最后由 终极讨厌 于 2008-6-19 09:32 编辑 [/i]]

我首先想到的是集合中的一个定理，定理名字忘了，但是内容是这样的：几个集合的并集的元素个数=每个集合的元素数目-至少2个集合交集中的元素数目+至少3个集合交集中的元素数目-4个...+5个.........直到所有集合的交集的元素数目。
于是就想出1个7-2个7+3个7-4个7....的算法。不知道对不对？

或者将这个数用8进制考虑....
错了...不考虑了..

[[i] 本帖最后由 Poshidon 于 2008-6-19 12:28 编辑 [/i]]

最后摸索出有7的规律了，整理如下：
70==>7+1
700==>7*10+7*9^0+1=134
7000==>133*10+7*9^1+1=1898
70000==>1897*10+7*9^2+1=24074


计算方法需要有点改动，还在整下，刚刚发的有点问题哈~

[[i] 本帖最后由 ycccc8202 于 2008-6-19 13:56 编辑 [/i]]

:lol :lol

UP楼上！！

[code]/**
* @function getNum  //---- 取得1-n的整数中有多少个含有数字k的数字
* @param n:uint //---- 1-n的整数范围
* @param k:uint //---- 含有数字k 范围是1-9
*/
function getNum(n:uint,k:uint):uint {
        if(k==0){
                trace("k的范围应该是1-9!")
                return 0;}
        var tempArr:Array=String(n).split("");
        trace(tempArr);
        var result:uint=0;
        var m:uint;
        while (tempArr.length) {
                m=uint(tempArr.shift());
                if (m==0) {
                        continue;
                }
                if (tempArr.length==0) {
                        if (m>=k) {
                                result++;
                        }
                        continue;
                }
                result+=getF(m,tempArr.length,k);
                if (m==k) {

                        return result + Number(tempArr.join(""));
                }
        }
        return result;
}
/**
* @function getF  //---- 首字母为m其余为0的计算  类似 80，900，4000等的计算求含有k的个数
* @param m:uint //---- 首位数字
* @param n:uint //---- 跟随的零的个数
* @param k:uint //---- 含有的数字k
*/
function getF(m:uint,n:uint,k:uint):uint {
        switch (true) {
                case m<k :
                        if (n==1) {
                                return m;
                        }
                        return getF(m,n - 1,k) * 10 + m * Math.pow(9,n - 1);
                case m==k :
                        if (n==1) {
                                return m + 1;
                        }
                        return (getF(m,n - 1,k) - 1) * 10 + m * Math.pow(9,n - 1) + 1;
                case m>k :
                        if (n==1) {
                                return m + 9;
                        }
                        return getF(m,n - 1,k) * 10 + (m - 1) * Math.pow(9,n - 1);

        }
        return null;
}
var n1:uint=2008080808;
var n2:uint=1000
var n3:uint=3979385;
trace(n1,"中有","<",getNum(n1,7),">","个",7);
trace(n2,"中有","<",getNum(n2,8),">","个",8);
trace(n3,"中有","<",getNum(n3,4),">","个",4);[/code]//现在可以计算出正整数范围内的含有数字k的个数了，k的范围是1-9,这里还不能计算出含有多少个0....含有0的还得找下规律：）


//大家可以用循环或者真循环来测试下，结果应该是吻合的，我这样总结出公式来计算效率就高了哈~


//以下是循环的检测方法,数字大了会很卡哦，不过用些小点的数字来验证下我上面公式的正确性[code]var n:uint=3979385
var result:uint;
for (var j:uint; j<=n; j++) {
if (String(j).indexOf("4")!=-1) {
  result++;
}
}
trace(result)[/code]

[[i] 本帖最后由 ycccc8202 于 2008-6-19 13:44 编辑 [/i]]

因为打字不如在本子上写字方便，所以在开始，我声明一个式子的意义：
C(n,r)  = n!/(r!*(n-r)!)——表示从n个元素取R个，不进行排列，即是组合。这里的"!"，也不是大家熟悉的逻辑运算符，而是阶乘运算符。
我在上面的帖子中提到过：1个7-2个7+3个7-4个7.....这里就讨论找7吧。
范围是1位数，0~9，那么结果是C(1,1)=1——只有一位，已经钉死是被找数了；
范围是2位数，00~99，C(2,1)*C(10,1)-C(2,2)*C(1,1)=2*10-1*1 = 19;开始的C(2,1)是从这2位数中选出7的选法，可以放十位，也可以放个位；C(10,1)很明确，当确定7后，别的位数可能的所有组合，这里也就是“1个7”的个数；C(2,2)*C(1,1)，C(2,2)是从2个数位中选2个数位来放2个7，C(1,1)是7放好后别的数和它的所有组合，这里也就是“2个7”的个数；
范围是3位数，000~999，C(3,1)*C(100,1)-C(3,2)*C(10,1)+C(3,3)*C(1,1)=300-3-+1=271；同上，1个7-2个7+3个7；
范围是4位数，0000~9999，C(4,1)*C(1000,1)-C(4,2)*C(100,1)+C(4,3)*C(10,1)-C(4,4)*C(1,1)=4000-600+40-1=3439;
根据xxx定理（我实在是记不得那外国人叫什么了）可得通项公式：
F(n)=(-1)^(n+1)*C(n,1)*C(10^n,1)
待求数N = Σ(1~n)F(n)————此处n是目标数的位数，式子表示以n为参数的通项公式从1到n求和。
有了这个公式，我们所要做的就是将目标数按照春叶大哥的方法拆解成10次幂的倍数和，即几个m*10^x的和，然后用这个m和公式相乘。待查数k的用处是用来和m比大小的，小于则直接相乘,若是大于或等于，则先相乘，计算出忽略首数所有符合的数目，然后单独计算仅首数符合，别的数位都不符合的数，很简单，C(9,1)^(n-1)=9^(n-1);
举个例子吧，2887，
2*271+(8*19+9^2)+(8*1+9^1)+(9^0)=793.
知道了被找数k究竟在这个问题中扮演什么样一个角色后，就不难解决"0"的问题了，其实它是所有情况中最简单的一种，因为它不用讨论在数首的问题。不过到目前为止，我都是0~9,00~99,000~999这样讨论的，而题目是从“1”开始，所以记得最后的结果要-1.
好了，啰嗦了许多，接下来写成程序去...

[code]
//=========组合===========
function comb(n:uint,r:uint):Number {
var N:Number = 1;
if (r>n/2) {
  r = n - r;
}
for (var i:uint = 0; i<r; i++) {
  N *= (n-i)/(r-i);
}
return N;
}

/*通项公式求和,先前的公式上标有误,
  更正之(-1)^(i+1)*C(n,i)*C(10^(n-i),1)*/
function F(n:uint):uint {
var N:uint;
  for (var i:uint = 1; i<=n; i++) {
  N += Math.pow((-1),(i+1))*comb(n,i)*comb(Math.pow(10,n-i),1);
}
return N;
}

//=====主函数==========
function main_fun(n:uint,k:uint):uint {
var N:uint;
var firstSameNumber:Boolean;
var tempArr:Array=String(n).split("");
tempArr.forEach(tempArrCallBack);
function tempArrCallBack(item:*,index:int,arr:Array) {
  var m:uint = uint(item);
  var n:uint = tempArr.length-index-1;
  if (!firstSameNumber) {//当首个等于k的数字没有出现时运行如下，出现了就终止
   if (m<k) {
    N += m*F(n);
   } else if (m==k) {
    firstSameNumber=true;
    N += m*F(n)+uint(tempArr.slice(index+1).join(""))+1;//当首个等于k的数字出现后，不再统计了，直接将后面的数字+1后累加到原来的N上；
    //trace(uint(tempArr.slice(index+1).join("")));
   } else {
    N += m*F(n)+Math.pow(9,n);
   }
  }
}
//====处理0的情况======
/*将0作为普通数字处理，得到N，然后考虑到0不能作为数首，
  于是将所有仅数首数字为0的数字排除，故而对所有首位为0，
  其它数位均不为0的数进行统计.
  */
if (k) {
  return N;
} else {
  var headIsZero:uint;
  for (var i:uint=0; i<tempArr.length; i++) {
   headIsZero += Math.pow(9,tempArr.length - i-1);//以4位数为例：0xxx,00xx,0x,0
  }
  //trace(N,headIsZero);
  return N - headIsZero;
}
}
trace(main_fun(2008080808,0));
trace(main_fun(2008080808,7));[/code]

我的确将0的情况轻看了。之前的想法有些地方欠妥。现在为了0牺牲了运行效率，采用的是将0当作普通数字统计，最后将特殊情况下——0作为数首的数字排除。不知道正确与否。只作抛砖引玉用。

恩，不错
这里把范围数字改成字符串形式的话，可以求很大的数字。

比如""2008080808200808080820080808082008080808200808080820080808082008080808""

因为我的方法中没有减法，所以反而能够得到结果
2.00668164238471e+69


//所以这里比较想知道没有减法参与的公式是杂样的，那样可以求很大的数字了

[[i] 本帖最后由 ycccc8202 于 2008-6-20 18:02 编辑 [/i]]

"没有减法参与的公式"不能理解这句话的意思。可以求很大的数字和有没有减法有什么关系呢？容斥原理中本来就是1+2-3+4-5+6-7+8-9..不过，我觉得春叶用的递归方法应该要好点吧，我在计算组合的时候，因为组合公式是C(n,r) = n!/r!*(n-r)!，而阶乘这个东西涨起来是很快的，几下就超过上限了，因此将公式化简成
function comb(n:uint,r:uint):Number {
var N:Number = 1;
if (r>n/2) {
  r = n - r;
}
for (var i:uint = 0; i<r; i++) {
  N *= (n-i)/(r-i);
}
return N;
}
这样是几个小数的累乘，虽然数学结果肯定是正整数，但是不敢保证计算机在这里计算的时候完全没有误差。可能范围数太大了，这个公式的误差累计就明显了吧，也就没有意义了。不过求2008080808,7的结果和春叶的一致。

虽然组合数肯定是uint的，但是我不知道计算机这样计算几个小数的累乘是否能保证是uint的，所以选择了Number

恩，是的~

我得好好学学公式,自己弄很痛苦，哈~

呵呵，探索精神很好啊，找出来0的规律没有？

恩，0的情况也找出规律，下面是完整的结果：[code]/**
* @author : CYPL
* @function getNum  //---- 取得1-n的整数字符串中有多少个含有数字k的数字
* @param n:uint //---- 1-n的整数范围
* @param k:uint //---- 含有数字k 范围是1-9
*/
function getNum(n:String,k:uint):Number {
        if (k>9) {
                return 0;
        }
        if (!isNaN(Number(n))) {
                n=Number(n).toString();
        } else {
                return 0;
        }
        var tempArr:Array=n.split("");
        var zlen:uint=tempArr.length;
        var result:Number=0;
        var m:uint;
        var obj:Object;
        while (tempArr.length) {
                m=uint(tempArr.shift());
                if (!k) {
                        if (!tempArr.length) {
                                break;
                        }
                        if (!m) {
                                result +=Number(tempArr.join(""))-(obj.k+1)*9;
                                break;
                        }
                        obj=getFObj0(m,tempArr.length);
                        result+=obj.result+(obj.k+1)*9;
                } else {
                        if (!m) {
                                continue;
                        }
                        if (!tempArr.length) {
                                if (m>=k) {
                                        result++;
                                }
                                break;
                        }
                        result+=getF(m,tempArr.length,k);
                        if (m==k) {

                                result +=Number(tempArr.join(""));

                                break;
                        }
                }
        }
        return result;
}
/**
* @function getF  //---- 首字母为m其余为0的计算  类似 80，900，4000等的计算求含有k的个数
* @param m:uint //---- 首位数字
* @param n:uint //---- 跟随的零的个数
* @param k:uint //---- 含有的数字k
*/
function getF(m:uint,n:uint,k:uint):uint {
        switch (true) {
                case m<k :
                        if (n==1) {
                                return m;
                        }
                        return getF(m,n - 1,k) * 10 + m * Math.pow(9,n - 1);
                case m==k :
                        if (n==1) {
                                return m + 1;
                        }
                        return (getF(m,n - 1,k) - 1) * 10 + m * Math.pow(9,n - 1) + 1;
                case m>k :
                        if (n==1) {
                                return m + 9;
                        }
                        return getF(m,n - 1,k) * 10 + (m - 1) * Math.pow(9,n - 1);

        }
        return null;
}
/**
* @function getFObj0  //---- 首字母为m其余为0的计算  类似 80，900，4000等的计算求含有0的个数的对象
* @param m:uint //---- 首位数字
* @param n:uint //---- 跟随的零的个数
*/
function getFObj0(m:uint,n:uint):Object {
        if (n==1) {
                return {result:m,k:-1};
        }
        var obj:Object=getFObj0(1,n-1);
        var k:uint=(obj.k + 1) * 9;
        obj={result:obj.result * 10 + 9 * k,k:k};
        m && (obj.result=obj.result*m+(m-1)*(k+1)*9);
        return obj;
}
var nStr1:String="62572457405820348";
var k1:uint=0;
var nStr2:String="2008080808";
var k2:uint=0;
var nStr3:String="2008080808";
var k3:uint=7;
trace(nStr1,"范围内含有",getNum(nStr1,k1),"个",k1);
trace(nStr2,"范围内含有",getNum(nStr2,k2),"个",k2);
trace(nStr3,"范围内含有",getNum(nStr3,k3),"个",k3);[/code]

偶

晕:b35

感谢你发表这么好的东东！

result:obj.result * 10 +

感谢你发表这么好的东东！

两问题想问一下

最好最快的方法

:)