ProjectEuler 483 Repeated permutation - 拼圖
By Kristin
at 2014-10-07T05:14
at 2014-10-07T05:14
Table of Contents
483. Repeated permutation
https://projecteuler.net/problem=483
我們把每一個改變數列{1, 2, 3, ..., n}元素順序的操作稱為一種重排。對於有n個
元素的集合則有n!種重排的方式(包括維持所有元素順序不動的操作)。當n = 3時
共有3! = 6種重排方式列舉如下:
- P_1 = 維持原順序不作更動
- P_2 = 交換第一、二個元素
- P_3 = 交換第一、三個元素
- P_4 = 交換第二、三個元素
- P_5 = 所有元素往右輪換一個位置
- P_6 = 所有元素往左輪換一個位置
如果反覆操作其中一種重排,則終將會回到一開始的順序。給定一重排P_i,令f(P_i)
為反覆操作P_i以得到原始順序的最小所需次數。例如,當n = 3時:
- f(P_1) = 1 : (1,2,3) → (1,2,3)
- f(P_2) = 2 : (1,2,3) → (2,1,3) → (1,2,3)
- f(P_3) = 2 : (1,2,3) → (3,2,1) → (1,2,3)
- f(P_4) = 2 : (1,2,3) → (1,3,2) → (1,2,3)
- f(P_5) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)
- f(P_6) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3)
令g(n)為給定數列長度n時,對所有P_i取f(P_i)^2的平均值。
g(3) = (1^2 + 2^2 + 2^2 + 2^2 + 3^2 + 3^2)/3! = 31/6 ≒ 5.166666667e0
g(5) = 2081/120 ≒ 1.734166667e1
g(20) = 12422728886023769167301/2432902008176640000 ≒ 5.106136147e3
請求出g(350),以科學記號表示答案至十位有效位數,並如同上面三個例子一般、
以小寫e作為真數與首數的區隔。
--
https://projecteuler.net/problem=483
我們把每一個改變數列{1, 2, 3, ..., n}元素順序的操作稱為一種重排。對於有n個
元素的集合則有n!種重排的方式(包括維持所有元素順序不動的操作)。當n = 3時
共有3! = 6種重排方式列舉如下:
- P_1 = 維持原順序不作更動
- P_2 = 交換第一、二個元素
- P_3 = 交換第一、三個元素
- P_4 = 交換第二、三個元素
- P_5 = 所有元素往右輪換一個位置
- P_6 = 所有元素往左輪換一個位置
如果反覆操作其中一種重排,則終將會回到一開始的順序。給定一重排P_i,令f(P_i)
為反覆操作P_i以得到原始順序的最小所需次數。例如,當n = 3時:
- f(P_1) = 1 : (1,2,3) → (1,2,3)
- f(P_2) = 2 : (1,2,3) → (2,1,3) → (1,2,3)
- f(P_3) = 2 : (1,2,3) → (3,2,1) → (1,2,3)
- f(P_4) = 2 : (1,2,3) → (1,3,2) → (1,2,3)
- f(P_5) = 3 : (1,2,3) → (3,1,2) → (2,3,1) → (1,2,3)
- f(P_6) = 3 : (1,2,3) → (2,3,1) → (3,1,2) → (1,2,3)
令g(n)為給定數列長度n時,對所有P_i取f(P_i)^2的平均值。
g(3) = (1^2 + 2^2 + 2^2 + 2^2 + 3^2 + 3^2)/3! = 31/6 ≒ 5.166666667e0
g(5) = 2081/120 ≒ 1.734166667e1
g(20) = 12422728886023769167301/2432902008176640000 ≒ 5.106136147e3
請求出g(350),以科學記號表示答案至十位有效位數,並如同上面三個例子一般、
以小寫e作為真數與首數的區隔。
--
Tags:
拼圖
All Comments
Related Posts
Puzzleup 2014 (10) Five-Letter Code
By Emma
at 2014-10-02T03:21
at 2014-10-02T03:21
清明上河圖拼圖
By Joseph
at 2014-10-01T23:18
at 2014-10-01T23:18
ProjectEuler 482 The incenter of a triangle
By Ethan
at 2014-09-28T22:03
at 2014-09-28T22:03
一個書上看到的題目
By Jacky
at 2014-09-28T08:40
at 2014-09-28T08:40
有人要跟團從amazon買益智玩具嗎?
By Skylar DavisLinda
at 2014-09-26T15:24
at 2014-09-26T15:24