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 阅读(1104) 评论(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

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

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

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

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

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


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