仙丹

仙丹

malic.xyz竞赛05 - Virtual Judge

思路

数学模型就是小于等于T的正整数中,有多少个数字仅含7,5,3并且7,5,3三个数都有。
最小的一个显然是357,次大的是375。
给具有这种性质的数字起个名字就叫“357数”。
如果一个数字仅含3,5,7,但可能不全含有,我们给这种性质的数字称为“偏357数”。
如果k是357数,那么给k后边续一位3,或者5,或者7的时候,它们仍然是357数。
如果k是“偏357数”,也是可能形成357数的,比如3335,后续一位7仍然能形成"357数"。
我们记下一个“偏357数”的三个状态:含有3,含有5,含有7。
函数f(int k,bool r3,bool r5,bool r7) 表示一个"偏357数"或"357数"k,当r3与r5与r7都是true时,k是357数,否则是偏357数。
如果k不大于T,为它后续一个3并令r3=true,后续5并令r5=true,后续7并令r7=true,这样新得到的数k10+3,k10+5,k10+7就是新的"偏357数"或"357数",就是调用要f(k10+3,true,r5,r7),f(k10+5,r3,true,r7),f(k10+7,r3,r5,true).每次调用f()先看k的三个标志位是否全为true,若是则增加计数。
直到当k超过T时结束判断,输出357数的计数结果。

除了用三个变量分别标明状态,还可以用一个数字作为标志位。r3,r5,r7表示分别用二进数001B,010B,100B表示,每次得到新的数就用标志进行按位或运算flag|1,flag|2,flag|4,当标志位flag是111B=7的时候说明此数是357数。

代码

def dfs(s,flag):
    if s>N:
        return 0
    ret =1 if flag==7 else 0
    ret+=dfs(s*10+3,flag|1)    
    ret+=dfs(s*10+5,flag|2)
    ret+=dfs(s*10+7,flag|4)
    return ret

N=int(input())
print(dfs(0,0))
#include <cstdio>
int N,count=0;
void dfs(long long,unsigned char);
int main(void)
{
    scanf("%d",&N);
    dfs(0,0);
    printf("%d\n",count);
    return 0;
}
void dfs(long long nextNum,unsigned char flag357)
{
    if(nextNum<=N)
    {
        if(flag357==07)    // 07 is BIN 111
            count++;
        dfs(nextNum*10+3,flag357|01); // BIN 001 续上3
        dfs(nextNum*10+5,flag357|02); // BIN 010 续上5
        dfs(nextNum*10+7,flag357|04); // BIN 100 续上7
    }
}

我在使用万能头文件的时候,出现了'count'变量定义模糊不明的问题。修改避免冲突即可。如'count2'

上一篇:北京大学2015年数学直博考试试题


下一篇:函数调用时栈在做什么?