今天的面试题做错了,呜呜

作者: 分类: 代码 时间: 2012-03-05 评论: 61条评论

题目是这样的:

有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问此后最大的f(n)=n的n是什么?

回学校,敲了一下自己当时写的代码,哎呀,错误百出啊。

当时,我是这样写的……

int f(int n,int count)
{
    if(n<10)
    {
        if(n==1) count++;
        return count;
    }
    
    if(n%10==1) count++;
    
    f(n/10,count);
}

int main()
{
    for(int i=1;i<100000;i++)
    {
        if(i==f(f))
        {
            printf("%d\n",i);
            getchar();
        }
    }
}

错到我都不忍心看了。错误点有以下:

1、递归的最终结果没有返回,应该是 return f(n/10,count); 才对。

2、我这个f函数,仅仅是求了n这个数中含的1而已嘛,离题万里。于是加了一个函数:

int f(int n)
{
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        sum += f(i,0);
    }
    return sum;
}

这个只需要一个参数的f,才是符合题意的f。

3、只是草率的随便写了一个返回去搜索,当然,我现在知道,在这个范围内一个符合要求的值也没有!!

正确的应该从0到0xFFFFFFFF,当然,这个时候不能用int了,而是unsigned int。


即使把这些全部改正过来,搜索效率也依然很低,因为f是一个循环。调用f的也是一个循环。

但是,我们知道n+1,其实就是在n的基础上加上n+1这个数中的1个个数,因此最终代码如下:

#include <windows.h>
#include <stdio.h>

//返回一个数字中包含"1"的个数
unsigned int f(unsigned int n,unsigned int count)
{
    if(n<10)
    {
        if(n==1) count++;
        return count;
    }
    
    if(n%10==1) count++;
    
    return f(n/10,count);
}

//效率低,重复计算,不使用
unsigned int f(unsigned int n)
{
    unsigned int sum = 0;
    for(unsigned int i=1;i<=n;i++)
    {
        sum += f(i,0);
    }
    return sum;
}


int main()
{
    double time = GetCurrentTime();
    unsigned int temp = 0; //保存上次计算结果
    for(unsigned int i=0;i<=0xFFFFFFFF;i++)
    {
        temp = f(i,temp);
        if(i==temp) printf("%u\n",i);
    }
    
    printf("Calc Over! %f",(GetCurrentTime()-time)/1000);
    getchar();
    return 0;
}

我计算的时候终点值是0x7FFFFFFF,因为那时候我没有改成unsigned int。而且已经能够得出答案,不用继续运行浪费时间。

 

还把另外一个不使用库函数实现strcpy的题目做成了实现strcat,我怎么了……o(︶︿︶)o 唉

最后贴一个简化版的代码,结果应该是199981。

#include <stdio.h>

int main()
{
    unsigned int count,num,temp;
    count = num = temp = 0;
    
    while(1)
    {
        temp = num;
        while(temp)
        {
            if(temp%10==1) count++;
            temp /= 10;
        }
        
        if(num==count) printf("%u\n",num);
        num++;
    }
    
    return 0;
}
标签: 面试经验

已有 61 条评论

  1. 猫毛卯帽
    猫毛卯帽

    这道题我把java写出来了,网盘:
    http://dl.dbank.com/c07tecicyk

    看不明白你做的,java应该比这代码简单

    希望,有空交流一下

    时间: 2012-03-11 22:17
  2. 猫毛卯帽
    猫毛卯帽

    这道题我用java写了一些

    f(n)=n 自1之后,就一直求不出了,我上限10000给它停了

    dl.dbank.com/c07tecicyk

    时间: 2012-03-11 22:22
    1. 耍下
      耍下

      我这上面的代码,求出第一个数:199981,耗时15ms(开了编译优化是0ms)。

      你可能没理解题意吧,f(13)=6是这样来的,1,(2-9忽略,不含1),10,11,12,13。这里一共出现了6个"1"。

      时间: 2012-03-11 22:38
      1. 猫毛卯帽
        猫毛卯帽

        你用myeclipse吗?应该没做错,
        就是不知道怎么优化我的程序了,java……纯控制台了……

        不知道你搞不搞java,求教优化~

        能email最好啦

        时间: 2012-03-12 20:58
        1. 猫毛卯帽
          猫毛卯帽

          cpp我没涉猎过,不过java弄不出到底是我被还是java悲呢。。。

          你的199981,我去试一下~

          时间: 2012-03-12 21:01
  3. cc
    cc

    看着很easy啊,这acm里的水题。

    时间: 2012-03-13 10:58
  4. testset
    testset

    o(∩_∩)o 哈哈,第一个好像是那个Google的题目哈

    时间: 2012-03-13 17:53
  5. test
    test

    <%
    dim i,c,d
    i=0
    c=0
    d=true
    do while d

    i=i+1 c=c+len(i)-len(replace(i,"1",""icon_wink.gif) if c&gt;=i and i&gt;1 then d=false

    loop
    response.write i
    %>

    评论内容有不少于一个中文汉字

    时间: 2012-03-14 12:54
  6. 啥也木有
    啥也木有

    f(13)=5吧...

    时间: 2012-03-18 12:48
  7. 啥也木有
    啥也木有

    额..11里面有2个1...

    时间: 2012-03-18 12:49
  8. cuterhei
    cuterhei

    // 或许

    include

    int f_n(int n, int refn)
    {

    int rawn = 0; int one_c = 0; int i = 0; for(; i 时间: 2012-03-18 22:18

评论已关闭