怎样将从1-200的数字完全打乱，但不许重复。
怎样将从1-200的数字完全打乱，但不许重复。
------------------------------------------
比如：
原来的顺序是：1 2 3 4 5... 200
打乱后的顺序可能是：188 156 2 9 32 34 67 ....(共200个数字，只是顺序杂乱无章)
最好保持较高的执行效率。
问题点数：20、回复次数：25Top
1 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-11-30 15:51:18 得分 3
#define SIZE 200
BYTE arr[SIZE];
BYTE i, j;
for ( i=0; SIZE!=i; ++i )
{
arr[ i ] = i;
}
srand( (unsigned)time( NULL ) );
for ( i=SIZE-1; 0!=i; --i )
{
j = rand() % (i+1);
arr[i] ^= ( arr[j] ^= ( arr[i] ^= arr[j] ));
}Top
2 楼chenzhichao2008（陈智超）回复于 2005-11-30 16:04:13 得分 3
using namespace std;
srand( time(0) );
shuffle( &arr[0], &arr[N] );Top
3 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-11-30 16:35:30 得分 0
STL 中应是“random_shuffle”函数（且无须先调用 srand 函数）。Top
4 楼chenzhichao2008（陈智超）回复于 2005-11-30 21:23:15 得分 0
哈哈，写错了,是random_shuffle
stl中的random_shuffle要调用srand的，不然每次都一样
Top
5 楼leeight（睡醒了！）回复于 2005-12-03 17:08:46 得分 3
int len = 200;
int[] a = new int[len];
int[] b = new int[len];
for(int i = 0 i < a.length; i ++){
int index = (int)(len * Math.rand());
b[i] = a[index];
len --;
swap(a[index], a[a.length - 1 - i]);
}Top
6 楼johnsuna（缘来是e）回复于 2005-12-05 16:40:43 得分 0
楼上的语句没有给数组a初始化值呀Top
7 楼wooley（云玄）回复于 2005-12-06 11:00:05 得分 1
發牌的代碼看看Top
8 楼ZeroGts（白水文方）回复于 2005-12-07 23:49:46 得分 1
随机地两两交换就可以了吧。Top
9 楼sanhill（）回复于 2005-12-08 09:52:35 得分 1
gxqcn(GxQ·< http://maths.myrice.com/ >)
程序不对，我实验过。
Top
10 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-12-08 11:29:17 得分 0
#define SIZE 200
BYTE arr[SIZE];
BYTE *p = arr, *pSwap;
BYTE k = 0;
while( SIZE != k )
{
*(p++) = ++k;
}
srand( (unsigned)time( NULL ) );
while( arr != --p )
{
pSwap = arr + ( rand() % --k );
*p ^= *pSwap ^= *p ^= *pSwap;
}Top
11 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-12-08 13:00:00 得分 4
以前的问题主要出在“交换变量”的代码上：“a ^= b ^= a ^= b”
当 a、b 是不同对象时，该算法可以达到快速交换的目的；
但当 &a==&b 时，则无论 a(b) 原来为多少，结果均为恒=0（∵ a^a=0，0^0=0）
以上是跟踪代码后的心得。
下面是较通用的、完整的代码：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
void ShowArr( int arr[], int arrLen )
{
int *p = arr, *p_end = arr + arrLen;
while( p_end != p )
{
printf("%d\t", *(p++));
}
system( "PAUSE" );
}
void RandArr( int arr[], int arrLen )
{
int k = arrLen;
int *p = arr + k;
int *pSwap;
while( arr != --p )
{
pSwap = arr + ( rand() % k ); // k = p - arr + 1
if ( p != pSwap )
{
*p ^= *pSwap ^= *p ^= *pSwap;
}
}
}
void main()
{
#define SIZE 200
int arr[SIZE];
int *p = arr;
int k = 0;
while( SIZE != k )
{
*(p++) = ++k;
}
ShowArr( arr, SIZE );
srand( (unsigned)time( NULL ) );
RandArr( arr, SIZE );
ShowArr( arr, SIZE );
}Top
12 楼xdop（鸿飞处）回复于 2005-12-08 16:31:28 得分 1
a=0时 ^任何值都是0
这样写实在有哗众取宠之感Top
13 楼xdop（鸿飞处）回复于 2005-12-08 16:32:43 得分 0
a=0时 ^任何值都是0
这样写实在有哗众取宠之感Top
14 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-12-08 17:35:46 得分 0
“a=0时 ^任何值都是0”
=====================
错矣！错矣！错矣！
一切仅是为了追求效率！Top
15 楼gxqcn（★) HugeCalc ← http://hugecalc.ik8.com/ (☆）回复于 2005-12-08 17:39:12 得分 0
修改笔误：
pSwap = arr + ( rand() % k ); // k = p - arr + 1
为
pSwap = arr + ( rand() % k-- ); // k = p - arr + 1
Top
16 楼zcz0918（）回复于 2005-12-13 14:24:01 得分 0
arr[i] ^= ( arr[j] ^= ( arr[i] ^= arr[j] ));
前面少了if（i != j）
这也是这种不要第三变量交换方式的弊端，自己和自己交换就变0了Top
17 楼sail988（小橡树）回复于 2005-12-13 19:12:33 得分 3
java JDK中提供的方法
public static int[] scramble(int size) {
int[] a = new int[size];
for (int i = a.length; --i >= 0;) {
a[i] = i;
}
for (int i = a.length; --i >= 0;) {
int j = (int)(i * Math.random());
int t = a[i];
a[i] = a[j];
a[j] = t;
}
return a;
}
传入参数200,它就给你一个长度为200的Top
18 楼johnsuna（缘来是e）回复于 2005-12-14 12:29:24 得分 0
嗯，楼上的代码精简。Top
19 楼Rick_ang（东方未名）回复于 2005-12-20 18:14:07 得分 0
用1-200不变,随机生成位置..用过的位置给个标记就行了Top
20 楼f_acme（沧海一声笑）回复于 2006-01-01 08:27:26 得分 0
既然用到Java了，不如直接使用Collections.shuffle（）方法就行了。Top
21 楼zhenming_liu（）回复于 2006-01-08 15:17:38 得分 0
hmm...saw this problem just now....
I got a question. How do you estimate the randomness (goodness) of an algorithm?
entropy wont work
K...blablaba...v complexity is not computatableTop
22 楼huang_ball（黄求）回复于 2006-01-14 08:22:08 得分 0
对数组的地址进行处理就行了，最的的就是用STL，请大家用一下再说
Top
23 楼goodboy1881（积木)(谁都别拦着我在水源升星）回复于 2006-01-14 12:01:54 得分 0
C++STL里面本身就有这样的函数。Top
24 楼wvins（逸岚）回复于 2006-01-16 10:17:19 得分 0
用1-200不变,随机生成位置..用过的位置给个标记就行了
//----------------------------------------------------------
同意
关键就是1-200
如果不是的话要麻烦一点
自己试吧!Top
25 楼sailor_Song（函数）回复于 2006-01-25 16:24:14 得分 0
取随即数啊，
简单的问题，Top
