| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1849 人关注过本帖, 1 人收藏
标题:我也来发个求排列的题
只看楼主 加入收藏
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 10楼 lz1091914999
是2的64次放 呵呵

至于你2楼代码提交RT 应该是这没考虑输入长度为1的情况
长度为1 end-2 就RT了
2012-06-01 15:54
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
回复 11楼 草狼
...

[ 本帖最后由 lz1091914999 于 2012-6-2 12:12 编辑 ]

My life is brilliant
2012-06-01 16:32
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:2 
回复 5楼 草狼
3楼 一语中的。无论K多大对这个程序没有多大的影响吧 只是把2^63以内的数k考虑下怎么搞是个输出形式出来 然后求   k = k % (n!) 在用这个去参与循环。所以是 n! 决定了变换的次数。

[ 本帖最后由 有容就大 于 2012-6-1 17:39 编辑 ]

梅尚程荀
马谭杨奚







                                                       
2012-06-01 17:32
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 13楼 有容就大
你可以实现下 看行不

输入
1
19 19!-1
1 2 3 4 5 6 7 8 9

看你的程序输出结果有多快
2012-06-01 17:48
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 12楼 lz1091914999
我也找不出了
2012-06-01 17:56
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:6 
第一步,仍然是k=k%(n!),此时(0<=0<n!)

我们把n=4时前8个排列列出来
程序代码:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3

我们可以看出对于第i个,它与第i+(4-1)!个的区别就是他它的第一位与之后的第一位交换即可,比如1 2 3 4与 2 1 3 4,找出规律后证明很简单,
所以算法就是:
程序代码:
for (k=n-1; k>=1; k--)
    while (m>=k!)
    {
        m-=k!; 按照上述规则变化;
    }

这个算法时间复杂度应该是O(N^3),应该没问题
2012-06-01 18:03
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 16楼 czz5242199
能给完整代码吗, 好研究
2012-06-01 18:18
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
你还是自己编吧,。。这个涉及到高精度运算,写起来太繁琐了
2012-06-01 18:21
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
或者这道题如果有oj的话,倒是可以试一下,今天刚考完离散数学,蛮闲的
2012-06-01 18:22
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
回复 18楼 czz5242199
我的代码n在20以后不需要高精度 且时间复杂度O(n^2)
2012-06-01 18:28
快速回复:我也来发个求排列的题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027055 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved