Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

列出所有9位数,它的前n位能被n整除

最简单的是穷举,不过那可要O(9*109),不可取 

#include <iostream>
#include 
<vector>
#include 
<algorithm>

using namespace std;

vector
<int> fun(int n)
{
    vector
<int> last,all;
    
int i,j,k;
    
for(i = 1;i < 10;++i)
        all.push_back(i);

    
if(n == 1)
        
return all;

    
int size;
    
int num;
    
for(i = 2;i <= n;++i)
    
{
        last 
= all;
        all.clear();
        size 
= (int)last.size();
        
for(j = 0;j < size;++j)
        
{
            
for(k = 0;k < 10;++k)
            
{
                num 
= last[j] * 10 + k;
                
if(num % i == 0)
                    all.push_back(num);
            }

        }

        last.clear();
    }


    
return all;
}

posted on 2007-04-16 17:29 Dain 阅读(1087) 评论(5)  编辑 收藏 引用 所属分类: 算法笔记

评论

# re: 列出所有9位数,它的前n位能被n整除 2007-04-17 00:16 踏雪赤兔

#include<ctime>
#include<iostream>
using namespace std;
int cnt=0;
void dfs(int s,int i){
if(i>9){
cout<<s<<endl;
cnt++;
return;
}
s*=10;
int m=s%i;
if(m!=0) m=i-m;
for(; m<10; m+=i) dfs(s+m,i+1);
}
int main(){
for(int j=0; j<10000;++j){
cnt=0;
for(int i=1; i<10; ++i) dfs(i,2);
// cout<<cnt<<endl;
}
cout<<clock();
return 0;
}
答案有2492个,不计输出用时约0.00058秒  回复  更多评论   

# re: 列出所有9位数,它的前n位能被n整除 2007-04-17 09:04 万连文

组合数学内容,早知道它很有用,可是还是忘记的差不多了,唉...  回复  更多评论   

# re: 列出所有9位数,它的前n位能被n整除 2007-04-19 17:17 wzqxp2002

我做出来是2227个  回复  更多评论   

# re: 列出所有9位数,它的前n位能被n整除 2007-04-19 19:52 wzqxp2002

是我看错了,是2492个  回复  更多评论   

# re: 列出所有9位数,它的前n位能被n整除[未登录] 2007-04-21 21:12 Dain

看下你的算法
@wzqxp2002
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理