版塊導(dǎo)航: 正在加載中...

登錄注冊

應(yīng)《網(wǎng)絡(luò)安全法》要求，自2017年10月1日起，未進(jìn)行實名認(rèn)證將不得使用互聯(lián)網(wǎng)跟帖服務(wù)。為保障您的帳號能夠正常使用，請盡快對帳號進(jìn)行手機(jī)號驗證，感謝您的理解與支持！

24小時熱門版塊排行榜

返回列表

holmescn

金蟲 (正式寫手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

[交流] Euler 工程第廿四題：全排列的第100萬項已有5人參與

一個排列是一組對象的一個有序排列。比如3123是數(shù)字1、2、3和4的一個可能的排列。如果把所有的排列按照其數(shù)字or字母的大小順序都列出來，那就成為一個全排列。比如0、1、2的全排列是：
012 021 102 120 201 210

那么，數(shù)字0、1、2、3、4、5、6、7、8和9的全排列的第100萬項是多少？

回復(fù)此樓

» 猜你喜歡

326求調(diào)劑已經(jīng)有8人回復(fù)
333求調(diào)劑已經(jīng)有7人回復(fù)
一志愿東華大學(xué)控制學(xué)碩320求調(diào)劑已經(jīng)有3人回復(fù)
考研化學(xué)學(xué)碩調(diào)劑，一志愿985 已經(jīng)有7人回復(fù)
化學(xué)工程321分求調(diào)劑已經(jīng)有21人回復(fù)
0703化學(xué)調(diào)劑已經(jīng)有15人回復(fù)
0703化學(xué)調(diào)劑，六級已過，有科研經(jīng)歷已經(jīng)有14人回復(fù)
326求調(diào)劑已經(jīng)有4人回復(fù)
311求調(diào)劑已經(jīng)有13人回復(fù)
311求調(diào)劑已經(jīng)有7人回復(fù)

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

Project Euler 50 歐拉工程 50 題已經(jīng)有12人回復(fù)
Project Euler 48 歐拉工程 48 題已經(jīng)有30人回復(fù)
Project Euler 45 歐拉工程 45 題已經(jīng)有7人回復(fù)
Euler 工程第四十一題已經(jīng)有5人回復(fù)
Euler 工程第廿九題：有多少不同的項? 已經(jīng)有30人回復(fù)
Euler 工程第廿六題：最長的循環(huán)節(jié) 已經(jīng)有9人回復(fù)
Euler 工程第十六題：2的1000次方的各項和已經(jīng)有14人回復(fù)
Euler 工程第十五題：從左上角到右下角有多少條路？已經(jīng)有5人回復(fù)
Euler Project Q13 歐拉工程第十三題已經(jīng)有20人回復(fù)
Euler Project Q12 歐拉工程第十二題已經(jīng)有23人回復(fù)
Euler 工程第十一題：相鄰元素乘積最大已經(jīng)有10人回復(fù)
Euler Project Q7. 歐拉工程第七題已經(jīng)有14人回復(fù)
Euler 工程第六題：平方和與和的平方差多少？已經(jīng)有5人回復(fù)
Euler 工程第二題：Fibonacci數(shù)列中小于4百萬的偶數(shù)的和已經(jīng)有8人回復(fù)

1樓 2011-06-10 10:27:10

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+5): 鼓勵交流~~ 2011-06-10 21:51:26

C++蠻力版代碼：

CODE:

#include 

#include 

#include 

using namespace std;

bool next_digit(char *first, char *last, char *end){

        char *left, *right;

        if(last-first<2){

                return false;

        }

        for(right = last; right > first; --right){

                for(left = right-1; left >= first; --left){

                        if(*left < *right){

                                if(!next_digit(left+1, right, end)){

                                        swap(*left, *right);

                                        sort(left+1, end);

                                        return true;

                                }else

                                        return true;

                        }

                }

        }

        return false;

}

string eular24(const string &str){

        char *base = const_cast(str.c_str());

        for(size_t i = 1; i < 1000000; ++i)

                next_digit(base, base+str.length()-1, base+str.length());

        return str;

}

int main(){

        cout<
        return 0;

}

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

2樓2011-06-10 11:45:00

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強(qiáng)帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+3): 謝謝分享~~ 2011-06-10 21:51:54

非蠻力版也有，不過不是自己想出來的，就不好意思直接貼代碼了，基本想法就是數(shù)制的擴(kuò)展：
二進(jìn)制數(shù)制是這個樣子：
a1*2^n+a2*2^(n-1)+...+an*2^1+a*2^0
十進(jìn)制數(shù)制是這樣子：
b1*10^n+b2*10^(n-1)+...+bn*10^1+b*10^0
那我們可以考慮階乘進(jìn)制：
c1*n!+c2*(n-1)!+...+cn*1!+c*0!
不過階乘有點(diǎn)問題就是1!是1，0!是0，那就失去了最后一個的意義，所以最后一個去掉：
c1*n!+c2*(n-1)!+...+cn*1!+c
那前面的6個數(shù)就依次是：
0=0*2!+0*1!+0 => 012
1=0*2!+1*1!+0 => 021
2=1*2!+0*1!+0 => 102
3=1*2!+1*1!+0 => 120
4=2*2!+0*1!+0 => 201
5=2*2!+1*1!+0 => 210
上面的計算當(dāng)然跟一般的進(jìn)制計算不同，一般的進(jìn)制計算是要求前面的數(shù)不能大過模數(shù)，二進(jìn)制的前綴只能是0和1，十進(jìn)制的前綴只能是0~9，而階乘進(jìn)制的前綴就只能是0~n，n是指后面的n!，以3=>120為例，前面的運(yùn)算應(yīng)該是這樣子：
2!：012，前綴就是take out的索引，例子的是1
1!：02，例子中的是1，拿走的就是2
0!：0，剩下來的沒得選擇，這也是每個末尾都是0的原因
組合起來就是120

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

3樓2011-06-10 12:04:56

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

wangww2011

木蟲 (著名寫手)

程序強(qiáng)帖: 13
應(yīng)助: 11 (小學(xué)生)
金幣: 4023.1
散金: 2709
紅花: 18
沙發(fā): 1
帖子: 1915
在線: 1537.1小時
蟲號: 772953
注冊: 2009-05-17
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

★ ★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+5): 鼓勵交流~~ 2011-06-10 21:52:10

c語言非蠻力版
當(dāng)時就亂寫了個也不清楚和上面的算法一樣不一樣

CODE:

#include 

#include 

char *euler24(int n){

        int a[10],i,j,i0;

        a[0]=1;

        for(i=1;i<10;i++)a[i]=a[i-1]*(i+1);

        for(i=0;i<10;i++){

                if(a[i]>=n){

                        i0=i+1;break;

                }

        }

        int b[i0];

        for(i=i0-2;i>=0;i--){

                b[i]=n/a[i];

                n%=a[i];

                if(n==0){

                        b[i]--;

                        n=a[i];

                }

        }  

        int p[i0];

        char str[i0+1];

        for(i=0;i

        for(i=0;i
                str[i]=p[b[i0-i-2]]+48;

                for(j=b[i0-i-2];j
                        p[j]=p[j+1];

        }

        str[i0-1]=p[0]+48;

        str[i0]='\0';

        return strdup(str);

}

int main(void){

        printf("%s\n",euler24(1000000));

        return 0;

}

[ Last edited by wangww2011 on 2011-6-10 at 13:28 ]

贊一下(2人)

回復(fù)此樓

4樓2011-06-10 13:24:31

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機(jī)軟件

★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+4): 鼓勵交流~~ 2011-06-10 21:52:28

python偷懶版

CODE:

# 2783915460

# Elapsed time: 0.35266074 seconds

import itertools

from mytictoc import tic, toc

tic()

m=itertools.permutations('0123456789')

for i in xrange(1000000-1):

    m.next()

print ''.join(list(m.next()))

toc()

贊一下(2人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

5樓2011-06-10 14:58:47

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

fatpig8832

鐵桿木蟲 (著名寫手)

應(yīng)助: 16 (小學(xué)生)
金幣: 7420.2
散金: 31
紅花: 28
帖子: 1438
在線: 610.9小時
蟲號: 770403
注冊: 2009-05-14

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+3): 歡迎參與~~ 2011-06-10 21:52:46

此題改小一點(diǎn)可以做初中或小學(xué)奧數(shù)題了...

10!=3628800, 10!/10=362880
1000000/362880=2.75------（0123456789）第一位是2
1000000-362880*2=274240
362880/9=40320
274240/40320=6.80------（013456789）第二位是7
274240-40320*6=32320
40320/8=5040
32320/5040=6.40------（01345689）第三位是8
32320-5040*6=2080
5040/7=720
2080/720=2.89------（0134569）第四位是3
2080-720*2=640
720/6=120
640/120=5.33------（014569）第五位是9
640-120*5=40
120/5=24
40/24=1.67------（01456）第六位是1
40-24*1=16
24/4=6
16/6=2.67------（0456）第七位是5
16-6*2=4
6/3=2
4/2=2------（046）第八位是4
此處已實現(xiàn)整除，后三位必為4開頭的最大數(shù)，即460.

所以最后結(jié)果為 2783915460...

贊一下(2人)

回復(fù)此樓

6樓2011-06-10 15:50:03

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強(qiáng)帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機(jī)軟件

★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
dubo(金幣+1): 歡迎常來程序語言版討論 2011-06-13 19:33:20

引用回帖:

Originally posted by fatpig8832 at 2011-06-10 15:50:03:
此題改小一點(diǎn)可以做初中或小學(xué)奧數(shù)題了...

10!=3628800, 10!/10=362880
1000000/362880=2.75------（0123456789）第一位是2
1000000-362880*2=274240
362880/9=40320
274240/40320=6.80------（013456789） ...

此法甚妙,一開始除362880的1000000是怎么來的?解釋下,謝謝了

贊一下(2人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

7樓2011-06-10 16:21:24

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

holmescn

金蟲 (正式寫手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

★ ★ ★
微塵、夢想(金幣+3): 鼓勵交流~~ 2011-06-10 21:53:27

暈，發(fā)晚了

樓上怎么沒人帖答案和時間了？

我的想法是利用階乘直接算。因為一個全排列，其實就是每個元素都要在一個位置上出現(xiàn)一次。這樣一共有n!個排列（這個地球人都知道）。
這樣，如果某一位確定了的話，那么其余的位再用其余的數(shù)全排列就行了。（這話怎么這么繞口）

已經(jīng)知道10!=3628800,9!=362880,這樣1000000 - 2*9! = 274240, 也就是說第一位取0,1都不夠數(shù)，取2，而后面的沒的完成全排列就夠100萬了。OK，第一位是2了。
下面列表：

8! = 40320  274240 - 6 * 8! = 32320 第2位：7
7! = 5040 32320  - 6 * 7! = 2080  第3位：8
6! = 720 2080 - 2 * 6! = 640 第4位：3
5! = 120 640 - 5 * 5! = 40 第5位：9
4! = 24    40    - 1 * 4! = 16 第6位：1
3! = 6    16    - 2 * 3! = 4    第7位：5
2! = 2    4    - 2 * 2! = 0

最后剩：0 4 6 這三個數(shù)了. 而最后一個余0了。也就是第2個排列正好就夠第100萬個了.這樣結(jié)果就是：2783915460

不知道結(jié)果是不是對。這個用時當(dāng)然很少的了。

贊一下(1人)

回復(fù)此樓

8樓2011-06-10 17:09:02

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

fatpig8832

鐵桿木蟲 (著名寫手)

應(yīng)助: 16 (小學(xué)生)
金幣: 7420.2
散金: 31
紅花: 28
帖子: 1438
在線: 610.9小時
蟲號: 770403
注冊: 2009-05-14

★
小木蟲(金幣+0.5):給個紅包，謝謝回帖

引用回帖:

Originally posted by libralibra at 2011-06-10 16:21:24:
此法甚妙,一開始除362880的1000000是怎么來的?解釋下,謝謝了

這個...不就是題目中的一百萬嗎...不過這不是編程而是死算，初中生甚至小學(xué)生都能搞出來...

8樓的做法應(yīng)該和我的一樣吧，雖然我沒怎么看懂...

贊一下(1人)

回復(fù)此樓

9樓2011-06-10 17:32:00

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

holmescn

金蟲 (正式寫手)

程序強(qiáng)帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

★ ★ ★
微塵、夢想(金幣+3): 鼓勵交流~~ 2011-06-10 21:53:45

python版代碼，算法剛才解釋過了。

CODE:

def fac(n):

    return reduce(lambda x, y: x*y, range(1, n+1))

n = 1000000

i = 9

numbers = range(10)

result = []

while i > 0 and n > 0:

    if n % fac(i) != 0:

        result.append(numbers[n/fac(i)])

    else:

        result.append(numbers[n/fac(i)-1])

    numbers.remove(result[-1])

    n  = n % fac(i)

    i -= 1

if len(numbers) > 0:

    numbers.reverse()

    result.extend(numbers)

print "".join([str(x) for x in result])

[ Last edited by holmescn on 2011-6-11 at 07:58 ]

贊一下(1人)

回復(fù)此樓

10樓2011-06-10 18:03:37

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

相關(guān)版塊跳轉(zhuǎn) 我要訂閱樓主 holmescn 的主題更新

返回列表

普通表情龍兔虎貓高級回復(fù) (可上傳附件)

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 299求調(diào)劑 +5	shxchem 2026-03-20	7/350	2026-03-21 17:09 by ColorlessPI
[考研] 299求調(diào)劑 +4	某某某某位 2026-03-21	4/200	2026-03-21 16:30 by barlinike
[考研] 306求調(diào)劑 +4	chuanzhu川燭 2026-03-18	4/200	2026-03-21 08:25 by laoshidan
[考研] 求調(diào)劑 +6	Mqqqqqq 2026-03-19	6/300	2026-03-21 08:04 by JourneyLucky
[考研] 一志愿山大07化學(xué) 332分四六級已過本科山東雙非求調(diào)劑！ +3	不想理你 2026-03-16	3/150	2026-03-21 03:59 by JourneyLucky
[考研] 310求調(diào)劑 +3	baibai1314 2026-03-16	3/150	2026-03-21 03:56 by JourneyLucky
[考研] 材料工程（專）一志愿985 初試335求調(diào)劑 +3	hiloiy 2026-03-17	4/200	2026-03-21 03:04 by JourneyLucky
[考研] 二本跨考鄭大材料306英一數(shù)二 +3	z1z2z3879 2026-03-17	3/150	2026-03-21 02:29 by JourneyLucky
[考研] 材料專碩英一數(shù)二306 +7	z1z2z3879 2026-03-18	7/350	2026-03-20 23:48 by JourneyLucky
[考研] 一志愿中海洋材料工程專碩330分求調(diào)劑 +8	小材化本科 2026-03-18	8/400	2026-03-20 23:16 by JourneyLucky
[考研] 一志愿南京理工大學(xué)085701資源與環(huán)境302分求調(diào)劑 +4	葵梓衛(wèi)隊 2026-03-18	6/300	2026-03-20 23:02 by JourneyLucky
[考研] 一志愿南理工085701環(huán)境302求調(diào)劑院校 +3	葵梓衛(wèi)隊 2026-03-20	3/150	2026-03-20 19:28 by zhukairuo
[考研] 環(huán)境工程調(diào)劑 +9	大可digkids 2026-03-16	9/450	2026-03-20 17:38 by 醉在風(fēng)里
[考研] 工科材料085601 279求調(diào)劑 +7	困于星晨 2026-03-17	9/450	2026-03-20 17:38 by 無懈可擊111
[考研] 085601材料工程專碩求調(diào)劑 +10	慕寒mio 2026-03-16	10/500	2026-03-19 15:26 by 丁丁*
[考研] 收復(fù)試調(diào)劑生 +4	雨后秋荷 2026-03-18	4/200	2026-03-18 14:16 by elevennnne
[考研] 材料，紡織，生物（0856、0710），化學(xué)招生啦 +3	Eember. 2026-03-17	9/450	2026-03-18 10:28 by Eember.
[考研] 生物學(xué)071000 329分求調(diào)劑 +3	我愛生物生物愛?/a> 2026-03-17	3/150	2026-03-18 10:12 by macy2011
[考研] 085601求調(diào)劑 +4	Du.11 2026-03-16	4/200	2026-03-17 17:08 by ruiyingmiao
[考研] 東南大學(xué)364求調(diào)劑 +5	JasonYuiui 2026-03-15	5/250	2026-03-16 21:28 by 木瓜膏

24小時熱門版塊排行榜

[交流] Euler 工程 第廿四題：全排列的第100萬項 已有5人參與

» 猜你喜歡

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

[交流] Euler 工程第廿四題：全排列的第100萬項已有5人參與