Dain

寫出一個可以工作的程序并不夠

公告

博學篤志格物明德

隨筆分類(16)

文章分類(7)

隨筆檔案(15)

文章檔案(5)

統計

隨筆 - 15
文章 - 5
評論 - 55
引用 - 0

留言簿(3)

積分與排名

積分 - 34190
排名 - 606

良師益友

cloudseawang
TerryLee技術專欄

閱讀排行榜

評論排行榜

列出所有9位數，它的前n位能被n整除

最簡單的是窮舉，不過那可要O(9*10⁹)，不可取

#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 閱讀(1151) 評論(5) 編輯收藏引用所屬分類: 算法、筆記

#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
回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: 列出所有9位數，它的前n位能被n整除最大的子序列和問題全排列算法求解(還沒有人做出來，唉) string和int間的類型轉換

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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