Project Euler Problem 276, 268, 347

〇〇 · 发表于 2012-1-20 09:57

〇〇发表于 2012-1-20 09:16
32行用i和index交换貌似不太随机，改成下面这样，24开头的小数就出来了

把交换改成随机取随机打乱，真的接近27

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAYSIZE 4
unsigned int inputArray[ARRAYSIZE]={1,3,2};
int c[3]={1,2,3};
int a[6][3]={{1,2,3},{2,1,3},{1,3,2},{2,3,1},{3,2,1},{3,1,2}};
int bozo()
{
int sorted = 1;
unsigned int index = 0;
unsigned int tmp = 0;
unsigned int iterationNo = 0;
unsigned int inputArraySize = 4;
unsigned int i=0;
//srand(clock());
//Checking if it's sorted
for(i = 0; i < inputArraySize - 1; i++)
{
if(inputArray[i] > inputArray[i + 1])
{
sorted = 0;
break;
}
}
//Bogosort Algorithm
while(sorted == 0)
{
//for(i = 0; i < inputArraySize; i++)
{
//pick and shuffle 3 values
index = (rand() % (inputArraySize ));
unsigned int index1 =index;
while(index==index1) index1=(rand() % (inputArraySize ));
unsigned int index2 =index;
while(index==index2 || index1==index2) index2=(rand() % (inputArraySize ));
c[0]=inputArray[index];
c[1]=inputArray[index1];
c[2]=inputArray[index2];
i=(rand() % 6);
inputArray[index]=c[a[i][0]-1];
inputArray[index1]=c[a[i][1]-1];
inputArray[index2]=c[a[i][2]-1];
}
sorted = 1;
iterationNo++;
//printf("%d ",iterationNo);
//Checking if it's sorted
for(i = 0; i < inputArraySize - 1; i++)
{
if(inputArray[i] > inputArray[i + 1])
{
sorted = 0;
break;
}
}
}
//printf("%d ",iterationNo);
return iterationNo;
}
int main(int argc, char **argv)
{
int sum=0;
int b[24][4]={{1,2,3,4},{2,1,3,4},{1,3,2,4},{2,3,1,4},{3,2,1,4},{3,1,2,4},
{4,1,2,3},{4,2,1,3},{4,1,3,2},{4,2,3,1},{4,3,2,1},{4,3,1,2},
{1,4,2,3},{2,4,1,3},{1,4,3,2},{2,4,3,1},{3,4,2,1},{3,4,1,2},
{1,2,4,3},{2,1,4,3},{1,3,4,2},{2,3,4,1},{3,2,4,1},{3,1,4,2}};
srand((unsigned) time(NULL));
for(int k=0;k<100;k++)
for(int i=0;i<24;i++) //7 don't finish
{
for(int j=0;j<4;j++)
{
inputArray[j]=b[i][j];
}
sum+=bozo();
}
printf("avg=%5.2f",sum/24.0/100);
return 1;
}

复制代码

newkid · 发表于 2012-1-20 23:34

你是用模拟的随机数验证，公式在哪里呢？

〇〇 · 发表于 2012-1-21 18:06

newkid 发表于 2012-1-20 23:34
你是用模拟的随机数验证，公式在哪里呢？

只能分析到2步，感觉又是什么连乘，最后要用傅立叶变换....
假设要把1234变成逆序
一次只允许变动其中3个
所有可能的结果是：
4不动 1/4概率
下面各种都是1/4*1/6=1/24概率
1234 --死循环
1324 *
2134
2314 *
3124 *
3214

3不动
1234 --重复
2134 --重复
1432
4132 *
4231 *
2431 *

2不动
1234 --重复2
4213 *
3214 --重复
3241 *
4231 --重复*
1243

1不动
1234 --重复3
1243 --重复
1324 --重复
1342 *
1423 *
1432 --重复
因为逆序需要4个，而一次只搬动3个，所以没有1种是能直接排好的,
再排一次，必须保证有个顺序对的数不动，比如4231的1不动或4不动
以4132为例
4不动的概率是1/4,排成4321的概率是1/24，加上第1次投，从这个路径2次成功的概率是1/24*1/24=1/576
但4231就不同,它第1次投就出现了2次
4不动，投另3个的成功的概率是1/6
1不动，投另3个的成功的概率是1/6
所以从这个路径2次成功的概率是1/4*1/6*2*1/4*1/6*2=1/144
这样这2条路径的概率是5/576，再算上其他的...*表示有可能2次成功的

〇〇 · 发表于 2012-1-21 19:03

〇〇发表于 2012-1-21 18:06
只能分析到2步，感觉又是什么连乘，最后要用傅立叶变换....
假设要把1234变成逆序
一次只允许变动其中3 ...

居然有这么多人解出来了

367 bozo sort 87

〇〇 · 发表于 2012-1-22 13:38

〇〇发表于 2012-1-21 18:06
只能分析到2步，感觉又是什么连乘，最后要用傅立叶变换....
假设要把1234变成逆序
一次只允许变动其中3 ...

第一步模拟出来了，第2步就是对每个结果，假定是abcd,再做出这么多种变换，记下概率
with t as(select level l from dual connect by level<=4)
,t2 as(select e,translate(e,'1234','abcd')g,
length(decode(instr(e,1),1,0)||decode(instr(e,2),2,0)||decode(instr(e,3),3,0)||decode(instr(e,4),4,0))f from(
select
a.l||b.l||c.l||d.l e
from t a,t b,t c,t d
where a.l not in(b.l,c.l,d.l)
and b.l not in(a.l,c.l,d.l)
and c.l not in(b.l,a.l,d.l)
and d.l not in(b.l,c.l,a.l)
)where instr(e,1)=1 or instr(e,2)=2 or instr(e,3)=3 or instr(e,4)=4 --至少一个位置不变的
)select * from t2;

E       G             F
---------- ---------- -----
4231    dbca          2
2431    bdca          1
3241    cbda          1
4132    dacb          1
1432    adcb          2
1342    acdb          1
4213    dbac          1
1423    adbc          1
1243    abdc          2
3214    cbad          2
2314    bcad          1
3124    cabd          1
1324    acbd          2
2134    bacd          2
1234    abcd          4

〇〇 · 发表于 2012-1-22 15:21

〇〇发表于 2012-1-22 13:38
第一步模拟出来了，第2步就是对每个结果，假定是abcd,再做出这么多种变换，记下概率
with t as(select l ...

假设对3214再bozo一次，得到的结果和概率分别是
with t as(select level l from dual connect by level<=4)
,t2 as(select e,translate(e,'1234','abcd')g,
length(decode(instr(e,1),1,0)||decode(instr(e,2),2,0)||decode(instr(e,3),3,0)||decode(instr(e,4),4,0))f from(
select
a.l||b.l||c.l||d.l e
from t a,t b,t c,t d
where a.l not in(b.l,c.l,d.l)
and b.l not in(a.l,c.l,d.l)
and c.l not in(b.l,a.l,d.l)
and d.l not in(b.l,c.l,a.l)
)where instr(e,1)=1 or instr(e,2)=2 or instr(e,3)=3 or instr(e,4)=4 --至少一个位置不变的
)select translate(a.e,1234,3214)g,a.f from t2 a;
G             F
---------- -----
4213          2
2413          1
1243          1
4312          1
3412          2
3142          1
4231          1
3421          1
3241          2
1234          2
2134          1
1324          1
3124          2
2314          2
3214          4

再把第一次bozo的各个结果全都加起来

with t as(select level l from dual connect by level<=4)
,t2 as(select e,translate(e,'1234','abcd')g,
length(decode(instr(e,1),1,0)||decode(instr(e,2),2,0)||decode(instr(e,3),3,0)||decode(instr(e,4),4,0))f from(
select
a.l||b.l||c.l||d.l e
from t a,t b,t c,t d
where a.l not in(b.l,c.l,d.l)
and b.l not in(a.l,c.l,d.l)
and c.l not in(b.l,a.l,d.l)
and d.l not in(b.l,c.l,a.l)
)where instr(e,1)=1 or instr(e,2)=2 or instr(e,3)=3 or instr(e,4)=4 --至少一个位置不变的
)select g ,sum(f) from
(select translate(a.e,1234,b.e)g,a.f*b.f f from t2 a,t2 b)group by g;

可见完成逆序操作（结果4321）的有16个

G             SUM(F)
---------- ----------
1234             48
1243             32
1324             32
1342             24
1423             24
1432             32
2134             32
2143             16
2314             24
2341             16
2413             16
2431             24
3124             24
3142             16
3214             32
3241             24
3412             16
3421             16
4123             16
4132             24
4213             24
4231             32
4312             16
4321             16

这样2次bozo，一共有24*24种，其中排序成功的有16种

〇〇 · 发表于 2012-1-22 16:00

〇〇发表于 2012-1-22 15:21
假设对3214再bozo一次，得到的结果和概率分别是
with t as(select level l from dual connect by level

扔4次的结果，可以分别记录每次成功的个数，然后一直扔，，，
with t as(select level l from dual connect by level<=4)
,t2 as(select e,--translate(e,'1234','abcd')g,
length(decode(instr(e,1),1,0)||decode(instr(e,2),2,0)||decode(instr(e,3),3,0)||decode(instr(e,4),4,0))f from(
select
a.l||b.l||c.l||d.l e
from t a,t b,t c,t d
where a.l not in(b.l,c.l,d.l)
and b.l not in(a.l,c.l,d.l)
and c.l not in(b.l,a.l,d.l)
and d.l not in(b.l,c.l,a.l)
)where instr(e,1)=1 or instr(e,2)=2 or instr(e,3)=3 or instr(e,4)=4 --至少一个位置不变的
)
,t3 as(select translate(a.e,1234,b.e)e,a.f*b.f f from t2 a,t2 b) --第2次扔
,t4 as(select translate(a.e,1234,b.e)e,a.f*b.f f from t2 a,t3 b where b.e<>4321)--排除掉第2次成功的
,t5 as(select translate(a.e,1234,b.e)e,a.f*b.f f from t2 a,t4 b where b.e<>4321)--排除掉第3次成功的
select e ,sum(f) from t5 group by e;

〇〇 · 发表于 2012-1-22 18:10

bogo 2次
with t2 as(
select 2134 e,1 f from dual union all
select 1324 e,1 f from dual union all
select 1243 e,1 f from dual union all
select 4231 e,1 f from dual union all
select 3214 e,1 f from dual union all
select 1432 e,1 f from dual
)select g ,sum(f) from
(select translate(a.e,1234,b.e)g,a.f*b.f f from t2 a,t2 b)group by g;

〇〇 · 发表于 2012-1-23 12:05

Problem 368[size=80%]22 January 2012

The harmonic series 1

+

1

2

+

1

3

+

1

4

+ ... is well known to be divergent.

If we however omit from this series every term where the denominator has a 9 in it, the series remarkably enough converges to approximately 22.9206766193.
This modified harmonic series is called the Kempner series.
Let us now consider another modified harmonic series by omitting from the harmonic series every term where the denominator has 3 or more equal consecutive digits. One can verify that out of the first 1200 terms of the harmonic series, only 20 terms will be omitted.
These 20 omitted terms are:

1

111

,

1

222

,

1

333

,

1

444

,

1

555

,

1

666

,

1

777

,

1

888

,

1

999

,

1

1000

,

1

1110

,

1

1111

,

1

1112

,

1

1113

,

1

1114

,

1

1115

,

1

1116

,

1

1117

,

1

1118

and

1

1119

.

This series converges as well.
Find the value the series converges to.
Give your answer rounded to 10 digits behind the decimal point.

〇〇 · 发表于 2012-1-23 19:57

〇〇发表于 2012-1-23 12:05
Problem 36822 January 2012

0806.4410.pdf (227.41 KB, 下载次数: 3)

NA-06-17.pdf (168.31 KB, 下载次数: 1)

0807.3518v1.pdf (151.6 KB, 下载次数: 4)

Project Euler Problem 276, 268, 347

浏览过的版块