一道迅雷笔试题
用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba
问题点数：20、回复次数：110Top
1 楼wanfustudio（雁南飞：知识之败,慕虚名而不务潜修也）回复于 2006-11-01 21:26:40 得分 20
void chang(char str[],int m)
/*定义循环左移函数(我没有用左移函数)*/
{
int i,j;
char temp=str[0];
for (i=0;i<m;i++) str[i]=str[i+1];
str[i]=temp;
}
void pai(char str[],int m,int n) /*定义全排列函数*/
{
int k;
void chang(char str[],int m);
if (m<n) /* 定 义 递 归 调 用 出 口 */
{
for (k=0;k<=m;k++)
{
pai(str,m+1,n); /*递归调用*/
chang(str,m); /*调用左移函数*/
}
}
else printf("%s\t",str);
}
#include "stdio.h"
main()
{char str[]="ABCD";
/*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
pai(str,0,4);
/*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch();
}
/*********************************************/
下面我来解释一下,我花了近1天的时间,找到这样一个规律如下:
┏ ABCD
┣ BCDA
┏ ABCD ━┫
┃ ┣ CDAB
┏ ABCD ━╋ BCAD ┗ DABC
┃ ┃ .
┃ ┗ CABD .
ABCD ━┫ .
┃ ┏ BACD .
┃ ┃ .
┗ BACD ━╋ ACBD ┏ CBAD
┃ ┣ BADC
┗ CBAD ━┫
┣ ADCB
┗ DCBA
简化图如下所示 ==>
┏ ABCD
┣ BCDA
┏ ABC ━┫
┃ ┣ CDAB
┏ AB ━╋ BCA ┗ DABC
┃ ┃ .
┃ ┗ CAB .
A ━┫ .
┃ ┏ BAC .
┃ ┃ .
┗ BA ━╋ ACB ┏ CBAD
┃ ┣ BADC
┗ CBA ━┫
┣ ADCB
┗ DCBA
Top
2 楼wanfustudio（雁南飞：知识之败,慕虚名而不务潜修也）回复于 2006-11-01 21:27:03 得分 0
┏ ABCD
┣ BCDA
┏ ABCD ━┫
┃ ┣ CDAB
┏ ABCD ━╋ BCAD ┗ DABC
┃ ┃ .
┃ ┗ CABD .
ABCD ━┫ .
┃ ┏ BACD .
┃ ┃ .
┗ BACD ━╋ ACBD ┏ CBAD
┃ ┣ BADC
┗ CBAD ━┫
┣ ADCB
┗ DCBA
简化图如下所示 ==>
┏ ABCD
┣ BCDA
┏ ABC ━┫
┃ ┣ CDAB
┏ AB ━╋ BCA ┗ DABC
┃ ┃ .
┃ ┗ CAB .
A ━┫ .
┃ ┏ BAC .
┃ ┃ .
┗ BA ━╋ ACB ┏ CBAD
┃ ┣ BADC
┗ CBA ━┫
┣ ADCB
┗ DCBA
Top
3 楼wanfustudio（雁南飞：知识之败,慕虚名而不务潜修也）回复于 2006-11-01 21:27:17 得分 0
晕，这个格式显示不出来～Top
4 楼OOPhaisky（异化$渴望成功~~）回复于 2006-11-01 21:27:56 得分 0
参考STL的相关方法的实现。Top
5 楼femalelover（楼主, 请把用不着的可用分捐给我1/3 ：（）回复于 2006-11-01 21:29:10 得分 0
雁南飞你这个是不是转帖啊, 怎么这么快的Top
6 楼pcboyxhy（-273.15℃）回复于 2006-11-01 21:31:57 得分 0
#include <stdio.h>
#include <stdlib.h>
char used[20]={0};
int number[20], len, i, p[20];
void output()
{
printf("\n");
for(i=0; i<len; ++i)
printf("%d ", number[p[i]]);
}
int pailie(int n)
{
int ii;
if(n==len)
output( );
for(ii=0; ii<len; ++ii)
if(!used[ii]){
used[ii] = 1;
p[n] = ii;
pailie(n+1);
used[ii] = 0;
}
return 0;
}
int main(int argc, char *argv[])
{
int index = 0;
scanf("%d", &len);
while(index<len)
scanf("%d", &number[index++]);
pailie(0);
return 0;
}
=====================================================================
#include <stdio.h>
#include <stdlib.h>
int number[20], len, temp;
void output()
{
int i;
printf("\n");
for(i=0; i<len; ++i)
printf("%d ", number[i]);
}
int pailie(int n)
{
int ii;
if(n==len)
output( );
for(ii=n; ii<len; ++ii){
temp = number[ii]; number[ii] = number[n]; number[n] = temp;
pailie(n+1);
temp = number[ii]; number[ii] = number[n]; number[n] = temp;
}
return 0;
}
int main(int argc, char *argv[])
{
int index = 0;
scanf("%d", &len);
while(index<len)
scanf("%d", &number[index++]);
pailie(0);
return 0;
}
=====================================================================
#include<stdio.h>
const int maxlen=9;
int num[9]={1,2,3,4,5,6,7,8,9};
void pailie()
{
int fenjie,i,j,k=maxlen-1,t;
char bb=1;
while(bb)
{
i=0;
while(i<=k)
printf("%d", num[i++]);
putchar('\n');
fenjie=k;
while(fenjie>0 && num[fenjie-1]>num[fenjie])
fenjie--;
if(fenjie)
{
j=k;
while(num[j]<num[fenjie-1])
j--;
i=num[j]; num[j]=num[fenjie-1]; num[fenjie-1]=i;
i=fenjie+k;
for(j=fenjie; j<=i/2; j++){
t=num[j];
num[j]=num[i-j];
num[i-j]=t;
}
}
else
bb=0;
}
}
==========================================================================
#include <stdio.h>
int num[]={12,12,14,14};
int main( void)
{
int fenjie, i, j, t, maxlen=4, k=maxlen-1;
char bb=1;
while(bb)
{
i=0;
while(i<k)
printf("%d ", num[i++]);
printf("%d\n", num[i++]);
fenjie=k;
while(fenjie>0 && num[fenjie-1] >= num[fenjie])
fenjie--;
if(fenjie){
j=k;
while(num[j]<=num[fenjie-1])
j--;
i=num[j]; num[j]=num[fenjie-1]; num[fenjie-1]=i;
i=fenjie+k;
for(j=fenjie;j<=i/2;j++){
t=num[j];
num[j]=num[i-j];
num[i-j]=t;
}
}
else
bb=0;
}
}
=========================================================================
其实STL的排列算法不错的
Top
7 楼femalelover（楼主, 请把用不着的可用分捐给我1/3 ：（）回复于 2006-11-01 21:32:00 得分 0
感觉还是有点难度的呀Top
8 楼g961681（技术庸人(情商太低)）回复于 2006-11-01 21:38:09 得分 0
http://down.cnzz.cn/info/7022.aspxTop
9 楼femalelover（楼主, 请把用不着的可用分捐给我1/3 ：（）回复于 2006-11-01 21:38:34 得分 0
雁南飞, 你在 pai函数中用了这么一句 void chang(char str[],int m); 编译时没有报错, 这个应该没有什么特殊的意义吧?Top
10 楼laiwusheng（风清扬）回复于 2006-11-01 21:48:31 得分 0
markTop
11 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-01 22:07:16 得分 0
全排列 (=_=)
我当场就作出来了Top
12 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-01 22:18:24 得分 0
void FooEx(char *str,char *substr);
void Foo(char *str){
char *temp=new char[strlen(str)+1] ;
strcpy(temp,str);
FooEx(temp,temp);
delete []temp;
}
void FooEx(char *str,char *substr){
if(*(substr+1)=='\0'){
cout<<str<<endl;
return;
}
char *p=substr;
while (*p!='\0'){
swap(*p,*substr);
FooEx(str,substr+1);
swap(*p,*substr);
++p;
}
}Top
13 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-01 22:19:16 得分 0
可惜还是没有受到offer
不知道当时参加最后面试的有谁收到offer的(=_=)Top
14 楼bowei3bowei3（听月轩）回复于 2006-11-01 22:57:08 得分 0
markTop
15 楼taodm（（不能收CSDN社区短信息，请莫浪费精力））回复于 2006-11-02 08:45:53 得分 0
全排列，我不做都出来了，stl里现成的。
next_permutationTop
16 楼Nowish（看我能忍耐多久）回复于 2006-11-02 08:58:35 得分 0
mark~Top
17 楼abomber2（走来走去）回复于 2006-11-02 09:12:24 得分 0
递归的问题Top
18 楼akirya（坏[其实偶不是什么所谓的坏人]）回复于 2006-11-02 09:22:01 得分 0
我写过，递归写嘛
粉好写的Top
19 楼fireinsnow（喜欢蓝色）回复于 2006-11-02 09:40:28 得分 0
markTop
20 楼ysc918（白纸人生）回复于 2006-11-02 09:42:13 得分 0
还得考虑str中有重复字符的情形吧Top
21 楼sms88（白板http://shop34112882.taobao.com）回复于 2006-11-02 09:46:46 得分 0
to SammyLan :
难道他们对递归的效率不满意??
Top
22 楼lpy2003（寒假应该干什么呢）回复于 2006-11-02 10:01:58 得分 0
不要忘记有个数据结构叫做栈
Top
23 楼bluer_ye（）回复于 2006-11-02 10:05:22 得分 0
递归是正解- -
so easyTop
24 楼yleiou（单刀匹马）回复于 2006-11-02 10:08:38 得分 0
这个实现感觉采用递归的方法比较好Top
25 楼aceouter（outer）回复于 2006-11-02 10:08:49 得分 0
全排列而已。Top
26 楼ysc918（白纸人生）回复于 2006-11-02 10:14:02 得分 0
下面的程序参考了有重复数字的无重复排列的方法。
要求字符串中字符升序(可以在排列前先排下序)
－－－－－－－－－－－－－－－－－
#include "stdio.h"
#include "math.h"
#define N 3
void OutPut(char a[N],int rec[N]);
void ArrangeK(char a[N],int rec[N],int used[N],int depth);
void main(void)
{
//char a[N]={'a','b','c','d','f'};
char *a="abb";
//char *b=sort(a);
int rec[N]={0};//下标
int used[N]={0};//是否已使用记录
ArrangeK(a,rec,used,0);
{
double (*p)(double)=sin;
printf("%lf\n",p(3.141593/6));
}
}
/*
* 输出，a--字符数组，rec[i]--第i个字符的下标
*/
void OutPut(char a[N],int rec[N])
{
for(int i=0;i<N;i++)
{
printf("%c ",a[rec[i]]);
}
printf("\n");
}
/*
* 有重复元素的无重复全排列
* 考察第depth个元素
*/
void ArrangeK(char a[N],int rec[N],int used[N],int depth)
{
//N?N-1
if(N==depth)
{
OutPut(a,rec);
}
else
{
char chPre=0;//前一个字符
for(int i=0;i<N;i++)
{
//当前字符未使用并且未重复
if(0==used[i] && a[i]>chPre)
{
chPre=a[i];//当前使用的字符
used[i]=1;//已使用
rec[depth]=i;//当前字符的下标为i
ArrangeK(a,rec,used,depth+1);//考察下一个字符
used[i]=0;//返回时，清除使用记录
}
}
}
}Top
27 楼xjflyttp（疯子nOvEr）回复于 2006-11-02 11:04:25 得分 0
提取第一个字符跟着追加到最后不就可以了````Top
28 楼milksnake（）回复于 2006-11-02 11:35:11 得分 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void FooEx(char *strhead, char *strtail)
{
int i=0;
int j=0;
int k=0;
if(strlen(strtail)==0)
{
printf("%s\n",strhead);
}
else
{
char *strEx1=(char *)malloc(sizeof(char)*((int)strlen(strhead)+2));
char *strEx2=(char *)malloc(sizeof(char)*(int)strlen(strtail));
strcpy(strEx1,strhead);
for(i=0;i<(int)strlen(strtail);i++)
{
strEx1[strlen(strhead)]=strtail[i];
strEx1[strlen(strhead)+1]='\0';
k=0;
for(j=0;j<(int)strlen(strtail);j++)
{
if(i==j)
continue;
strEx2[k]=strtail[j];
k++;
}
strEx2[k]='\0';
FooEx(strEx1,strEx2);
}
free(strEx2);
free(strEx1);
}
}
void Foo(const char *str)
{
FooEx("",str);
}
main()
{
Foo("abc");
}
很久没写了……居然花了一个多小时，惭愧ingTop
29 楼milksnake（）回复于 2006-11-02 11:40:04 得分 0
发现没有考虑重复字符的问题啊。。。还是太naive了Top
30 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-02 11:54:02 得分 0
sms88(白板)
to SammyLan :
难道他们对递归的效率不满意??
to 白板
不是那原因,技术方面过关了,还进入了他们的最后面试
只是跟我一起进入面试的三十多号人都算比较NB吧
除了我一个是华师之外,其他的都是中大华工的,还有几个是研究生(=_=)
MD,迅雷也不是什么大公司 ,居然吸引了那么多中大华工的
Top
31 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-02 11:56:16 得分 0
不知道中大华工的有没有人收到offer
我当时面试完问那面试官什么时候能知道结果,他的答复是一个月之内
我的天那,他们开始说好面试完就给offer的,现在说一个月之内,那不是摆明将我婉拒了么Top
32 楼icedatura（）回复于 2006-11-02 12:10:56 得分 0
#include <iostream.h>
#include <conio.h>
bool InPrint(char *print, char c, int pleng);
void Print(char *array, char *print, int pi, int leng);
int main(){
char array[4] = {'a','b','c','d'};
char print[4];
Print(array, print, 0, 4);
getch();
}
bool InPrint(char *print, char c, int pleng){
bool find = false;
for(int i=0; i<pleng; i++)
if(print[i] == c){
find = true;
break;
}
return find;
}
void Print(char* array, char* print, int pleng, int leng){
bool add = false;
for(int i=0; i<leng; i++){
if(!InPrint(print, array[i], pleng)){
add = true;
print[pleng] = array[i];
Print(array, print, pleng+1, leng);
}
}
if(!add){
for(int i=0; i<pleng; i++)
cout<<print[i];
cout << "\t";
}
}Top
33 楼qxbnit（蓝灵）回复于 2006-11-02 12:17:59 得分 0
to 白板
不是那原因,技术方面过关了,还进入了他们的最后面试
只是跟我一起进入面试的三十多号人都算比较NB吧
除了我一个是华师之外,其他的都是中大华工的,还有几个是研究生(=_=)
MD,迅雷也不是什么大公司 ,居然吸引了那么多中大华工的
---------
看来学历还是会压死一些人的....Top
34 楼robinken（勇）回复于 2006-11-02 13:40:36 得分 0
楼上的兄弟啊！不知道你有没有去测试你自己写的那个程序。当你输入ABC的时候。会输出正确的全排列的形式。但是当你输入ABCDEFG等长的字符串的时候呢？你看看会输入什么来呢？好像会少了很多全排列的数据。Top
35 楼robinken（勇）回复于 2006-11-02 13:42:47 得分 0
wanfustudio(雁南飞:知识之败，慕虚名不务潜修也)
我不知道你有没有测试你自己的程序。你写的那个程序是有问题的。有局限型的。你去找一找啊！输入abc可以出来结果。但是你输入的字符串在长一点看看。会死循环出不来。我测试过。当字符串长度到达7的时候就跳不出来。死循环中了。Top
36 楼sms88（白板http://shop34112882.taobao.com）回复于 2006-11-02 13:45:32 得分 0
to SammyLan(珍惜生命,远离UI)
迅雷 现在有钱啊,拿到很多风险投资
我现在就在做UI方面的工作,郁闷!Top
37 楼luoqintao（tooluck）回复于 2006-11-02 14:05:26 得分 0
中间如果有重复的，你们的算法还适用么，比如abcda，这里有俩a。Top
38 楼popchild（欧罗巴骚客贩）回复于 2006-11-02 14:07:09 得分 0
wanfustudio可以去迅雷了Top
39 楼csShooter（Sharp Shooter）回复于 2006-11-02 14:17:26 得分 0
markTop
40 楼pcboyxhy（-273.15℃）回复于 2006-11-02 14:19:37 得分 0
我贴的第四个就是专门针对有重复的情况的Top
41 楼milksnake（）回复于 2006-11-02 15:30:09 得分 0
To robinken(勇)
呵呵，那是因为排列数太多了，前面的看不到了
把printf("%s\n",strhead);改成printf("%s ",strhead);试试，会多看到一些数据的Top
42 楼femalelover（楼主, 请把用不着的可用分捐给我1/3 ：（）回复于 2006-11-02 16:09:18 得分 0
没想到这个铁子上首页了。
迅雷没什么前途的， 人家一告他侵权， 他就要关门啦。
工资5000左右，中等偏上。Top
43 楼femalelover（楼主, 请把用不着的可用分捐给我1/3 ：（）回复于 2006-11-02 16:12:50 得分 0
感觉大家都比较NB， 不过如果要你真的写一个可用的出来， 能的人估计就不多了。
上面有人说用STL，那肯定直接OUT 了， 因为你会错了命题人的意啦 ：）Top
44 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-02 16:19:45 得分 0
sms88(白板) ( ) 信誉：99 Blog 2006-11-2 13:45:33 得分: 0
to SammyLan(珍惜生命,远离UI)
迅雷 现在有钱啊,拿到很多风险投资
我现在就在做UI方面的工作,郁闷!
白板在迅雷做UI?Top
45 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-02 16:24:50 得分 0
迅雷的笔试题目出得很没有水平(=_=)
C++的居然连模板跟继承多态都不考
算法题目要么太大,要么太偏,考察不出真正的水平,感觉就一道题目比较实用的(=_=)
跟他们市场部经理以及那个金波说过他们试题的缺点了,并给了不少建议
估计下面接着的笔试会增加难度,其他省市的孩子们,节哀吧(=_=)Top
46 楼swimmer2000（时间是用来浪费的,所以每当我做了一点事都觉得很自豪）回复于 2006-11-02 18:19:28 得分 0
mark下.Top
47 楼swimmer2000（时间是用来浪费的,所以每当我做了一点事都觉得很自豪）回复于 2006-11-02 21:21:28 得分 0
贴下俺的做法,算法类似插入排序.
#include <iostream>
#include <string>
using namespace std;
void test(char * pch, char * buffer)
{
if (!strlen(buffer))
{
cout << string(pch) << endl;
return;
}
int len = strlen(pch);
char * pTemp = new char[len + 1];
strcpy(pTemp, pch);
for(int i = 0; i <= len; i++)
{
strncpy(pch, pTemp, i);
pch[i] = *buffer;
strcpy(pch + i + 1, pTemp + i);
test(pch, buffer + 1);
}
delete[] pTemp;
};
void TestFunc(char * pstr)
{
if (!pstr)
return;
char * pch = new char[strlen(pstr) + 1];
memset(pch, 0, strlen(pstr) + 1);
test(pch, pstr);
delete []pch;
};
void main()
{
char ch[] = "abcd";
TestFunc(ch);
}Top
48 楼hasgone（冷锋）回复于 2006-11-02 21:35:16 得分 0
- -!
敢不敢递归一下Top
49 楼xuleicsu（）回复于 2006-11-03 15:11:50 得分 0
用递归
很简单的Top
50 楼Could（翻墙鹦鹉）回复于 2006-11-03 15:57:02 得分 0
迅雷就是做下载软件的那个？
都有公司了？Top
51 楼genius_hb（本人很差）回复于 2006-11-03 18:45:07 得分 0
。。。字符串的大小吧，stl中有Top
52 楼sms88（白板http://shop34112882.taobao.com）回复于 2006-11-03 18:58:56 得分 0
to SammyLan
让你误解了,我不在迅雷
UI其实我并不喜欢做.害得我好多C++都在淡忘Top
53 楼zerooloo（）回复于 2006-11-04 19:50:38 得分 0
#include "iostream"
#include "cstring"
using namespace std;
void foo(char *str,int m)
{
int i;
int j;
char t;
if(m==1)
{
for( j=strlen(str)-1;j>=0;j--)
cout<<str[j];
cout<<endl;
}
else
{
for( i=0;i<m;i++)
{
//右移
t=str[i];
for( j =i;j<m-1;j++)
{
str[j]=str[j+1];
}
str[m-1]=t;
foo(str,m-1);//递归
//左移，恢复
t=str[m-1];
for( j =m-1;j>i;j--)
{
str[j]=str[j-1];
}
str[i]=t;
}
}
}
void main(void)
{
char str[5]="abcd";
foo(str,strlen(str));
}Top
54 楼dead_of_winter（寒冬）回复于 2006-11-04 20:24:25 得分 0
全排列倒是好说
我最近想写个n元集的r排列 感觉很难下手 似乎一个函数搞不定？Top
55 楼qozms（Alex）回复于 2006-11-04 20:45:44 得分 0
markTop
56 楼sinall（）回复于 2006-11-04 21:35:19 得分 0
呵呵，来给大伙说说原理：
A(n,n) = n!
=>A(n,n) = A(n-1,n-1)*n
有了递推公式，就可以写递归函数了：
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
typedef vector<string> Permutation;
typedef vector<string>::iterator PmtIterator;
// 计算templet字符串中从pos位置开始的全排列
Permutation permute(const string& templet, string::size_type pos)
{
Permutation temp;
if (pos == templet.size()-1)
{
temp.push_back(string(1, templet[templet.size()-1]));
}
else
{
// 计算从pos+1开始的全排列sub
// 然后就sub的每一项，计算出pos位置开始的全排列
Permutation sub = permute(templet, pos+1);
for (PmtIterator iter = sub.begin(); iter != sub.end(); ++iter)
{
for (string::size_type pos1 = 0; pos1 <= iter->size(); ++pos1)
{
temp.push_back(*iter);
temp[temp.size()-1].insert(pos1, 1, templet[pos]);
}
}
}
return temp;
}
int main(void)
{
string templet = "abc";
Permutation pmt = permute(templet, 0);
copy(pmt.begin(), pmt.end(), ostream_iterator<string>(cout, " "));
cout << endl;
return 0;
}Top
57 楼pappGG（天天向上）回复于 2006-11-04 23:41:41 得分 0
好像都用递归，咱来个循环的，应该比递归快
============一道迅雷笔试题_字符串全排列.cpp================
#include <stdio.h>
#include <string.h>
int Foo(const char *str)
{
size_t len = strlen(str);
int * range = new int[len];
int cont, i, j, counter = 0;
memset(range, 0, len*sizeof(int));
while(1){
for(i=0; i<len; i++){
if(++range[i]>=len) range[i] = 0;
else break;
}
if (i==len) break;
for(i=0,cont=0; i<len-1; i++){
for(j=i+1; j<len; j++){
if(range[i]==range[j]) cont=1;
}}
if (cont) continue;
for(i=0; i<len; i++)
printf("%c", str[range[i]]);
printf("\n");
++counter;
}
delete [] range;
return counter;
}
int main(int argc, char** argv)
{
printf("count: %d\n", Foo("abcdefgh"));
return 0;
}
==========================================================
Top
58 楼xiao2004（）回复于 2006-11-05 00:35:47 得分 0
这么简单的题吗？
#include <iostream>
using namespace std;
void xunlei(char *rstr);
int
main ( int argc, char *argv[] )
{
char s[]="abc";
xunlei(s);
return 0;
} /* ---------- end of function main ---------- */
void xunlei(char *rstr)
{
int max = strlen(rstr);
for(int i =0; i<max; i ++)
for(int j =0;j<max;j++)
for(int k=0;k<max;k++)
{
if(i != j && j!=k &&i !=k)
printf("%c%c%c\n",rstr[i],rstr[j],rstr[k]);
}
}
Top
59 楼Edison1024（留取钱财照汗青）回复于 2006-11-06 00:46:19 得分 0
楼上，把你贴删了吧，简直出来丢人啊。。。。。搞笑也不是你这么个搞法吧。Top
60 楼wlwlxj（wlwlxj）回复于 2006-11-06 10:49:06 得分 0
组合数学问题
^_^Top
61 楼pigo（）回复于 2006-11-06 10:49:51 得分 0
迅雷是当面确定offer。
我当时去面试的时候仅仅作为普通工程师的待遇开的是7k/月，有3000股期权。
（普通工程师上面还有工程师，高级工程师，系统工程师，伙伴工程师）.
Top
62 楼lw1a2（一刀 现在改六点下班了：（）回复于 2006-11-06 11:20:37 得分 0
回溯，排列树.....Top
63 楼arbiter（同济流氓）回复于 2006-11-06 11:39:18 得分 0
构建图模型，并深度遍历之，找到所有路径。Top
64 楼SammyLan（(基础决定你能走多远)--英语菜才是真的菜）回复于 2006-11-06 13:02:15 得分 0
pigo() ( ) 信誉：100 Blog 2006-11-06 10:49:00 得分: 0
迅雷是当面确定offer。
我当时去面试的时候仅仅作为普通工程师的待遇开的是7k/月，有3000股期权。
（普通工程师上面还有工程师，高级工程师，系统工程师，伙伴工程师）.
伤心(=_=)
Top
65 楼chenhui530（陈辉）回复于 2006-11-06 13:04:50 得分 0
不会VC用VB完成了不知道对吗大家检查下
Private Sub Form_Load()
Dim str As String, strTmp, strTemp As String
'str = "abcdef"
str = "abcd"
Dim i, j As Integer
For i = 1 To Len(str)
strTmp = Mid(str, i, 1)
strTemp = Left(str, i - 1) & Mid(str, i + 1, Len(str) - (i - 1))
For j = 1 To Len(strTemp)
List1.AddItem strTmp & Left(strTemp, j - 1) & Mid(strTemp, j + 1, Len(strTemp) - (j - 1)) & Mid(strTemp, j, 1)
Next
Next
End SubTop
66 楼khzhang（Odin）回复于 2006-11-06 13:50:17 得分 0
#include<iostream.h>
void swap(char str[],int x, int y)
{
int temp;
temp=str[x];
str[x]=str[y];
str[y]=temp;
}
void print(char str[])
{
for(int i=0; i < 4; i++)
cout<<str[i];
cout<<endl;
}
void foo(char str[],int position,int strlen)
{
if(position==strlen)
print(str);
else
{
for(int i=position; i < strlen; i++)
{
swap(str,i,position);
foo(str,position+1,strlen);
swap(str,i,position);
}
}
}
int main()
{
char str[]="abcd";
foo(str,0,4);
return 0;
}Top
67 楼yujiasw（）回复于 2006-11-06 14:03:42 得分 0
用C#写了一个
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
CPL pl = new CPL(11);
DateTime s = DateTime.Now;
//int[] t;
//do
//{
// t = pl.CurrentPL();
// for (int i = 0; i < t.Length; i++)
// {
// Console.Write(string.Format("{0} ", t[i]));
// }
// Console.WriteLine();
//}
while (pl.Next());
TimeSpan sp= DateTime.Now - s;
Console.WriteLine(sp);
}
}
public class CPL
{
private int MaxIndex;
private int[] pllist;
public CPL(int length)
{
pllist = new int[length];
MaxIndex = length - 1;
for (int i = 0; i < length; pllist[i] = i, i++);
}
public int[] CurrentPL()
{
return pllist;
}
public bool Next()
{
int indexA = FindLatestSmaller();
if (indexA < 0) return false;
int indexB = FindNextBigger(indexA);
int temp = pllist[indexA];
pllist[indexA] = pllist[indexB];
pllist[indexB] = temp;
ReverseLast(indexA + 1);
return true;
}
int FindLatestSmaller()
{
for (int i = MaxIndex - 1; i >= 0; i--)
{
if (pllist[i+1] > pllist[i])
return i;
}
return -1;
}
int FindNextBigger(int index)
{
for (int i = MaxIndex; i > index+1; i--)
{
if (pllist[i] > pllist[index])
return i;
}
return index + 1;
}
void ReverseLast(int index)
{
int temp;
int TwoMid = MaxIndex + index;
for (int i = index; i <= TwoMid / 2; i++)
{
temp = pllist[TwoMid - i];
pllist[TwoMid - i] = pllist[i];
pllist[i] = temp;
}
}
}
}
我测试了一下，效率还是比较高的，我2.0G的CPU，计算12个数的全排列不到20秒。Top
68 楼yujiasw（）回复于 2006-11-06 14:09:22 得分 0
如果字符串的话，就把上面的输出的值(int型)作为索引就好了。
如果有重复字符，但要求结果不重复的话。还要再输出的时候做重复性检查。
Top
69 楼redlive（）回复于 2006-11-06 15:00:12 得分 0
用Delphi做彩票软件时涉及的排列函数，结果放于文件中。setCount:元素个数，elementCount:排列个数;fileName:输出文件名;返回排列个数。
function combination( setCount:integer;elementCount:integer;fileName:string;total:int64):int64;
var
setArray:array of integer;
i,j:integer;
outf:textFile;
str:string;
income:boolean;
begin
result:=0;
assignFile(outf,fileName);
rewrite(outf);
setLength(setArray,elementCount);
i:=0;
setArray[0]:=1;//初始数组
while i>=0 do
begin
while i<elementCount-1 do
begin
setArray[i+1]:=setArray[i]+1;
inc(i);
end;
str:='';
for j:=0 to elementCount-2 do//取前几个数字
str:=str+myinttostr(setArray[j],2);
for j:=setArray[i] to setCount do//循环最后一位
begin
writeLn(outf,str+myinttoStr(setArray[i],2)); //写文件
inc(setArray[i]);
inc(result);
//
end;
income:=true;//进位
while income do
begin
dec(i);
if i>=0 then
begin
inc(setArray[i]);
income:=(setArray[i]>setCount);
end
else
begin
income:=false;
end;
end;
end;
closefile(outf);
end;Top
70 楼welfarefanwei（伟大）回复于 2006-11-06 15:00:17 得分 0
Mark 笔试题Top
71 楼redlive（）回复于 2006-11-06 15:12:46 得分 0
刚才发错了，发成组合的了，排列的做法是判断方法不一样，思路一样。Top
72 楼netdata（代码）回复于 2006-11-06 15:26:03 得分 0
mark
yujiasw() c#,没用过这个,不知道怎么样...Top
73 楼foollish（）回复于 2006-11-06 15:28:06 得分 0
#include <iostream>
// 从零到几的全排列，现在是到5的
#define MAXSIZE 5
typedef unsigned short byte;
struct Buffer
{
byte data[MAXSIZE];
byte len;
public:
void clear()
{
memset( data, 0, sizeof(data) );
this->len = 0;
}
int find( int a )
{
for( int i = 0; i < this->len; i++ )
{
if( this->data[i] == a )
return i;
}
return 0;
}
};
void foo( Buffer& buf );
void main()
{
Buffer buffer;
buffer.clear();
buffer.len = MAXSIZE;
foo( buffer );
}
void foo( Buffer& buf )
{
int pos, size, i;
i = 0;
pos = 0;
size = 0;
while( i < buf.len )
{
size = buf.data[i] > size ? buf.data[i] : size;
i ++;
}
if( size == MAXSIZE )
{
int outTemp[MAXSIZE];
for( int ii = 0; ii < buf.len; ii++ )
{
outTemp[ii] = buf.find( size-- );
std::cout << outTemp[ii] << " ";
}
std::cout << std::endl;
return;
}
for( int ii = 0; ii < buf.len; ii++ )
{
if( ( buf.data[ii] == 0 ) && ( ii >= pos ) )
{
buf.data[ii] = size + 1;
pos = ii;
foo( buf );
buf.data[ii] = 0;
}
}
}
Top
74 楼foollish（）回复于 2006-11-06 15:41:06 得分 0
自己写的，以前写银行家算法的时候写过，都忘了，重新写花了一个半小时，惭愧了。。。
改变MAXSIZE的大小可以计算几个算的排列。这个是算数字排列的，适当的改变size的定义就可以算其他的（字母，class。。）的排列了。有什么错误希望大家指出。
小弟先谢了~Top
75 楼NsGFr（elan）回复于 2006-11-06 17:16:26 得分 0
http://ephon.spaces.live.com/blog/cns!796FAD06E2C0A525!431.trak
---------------------------
奶奶的，字符超过８个慢死了，就有可能oom...Top
76 楼wulei5482（忍者）回复于 2006-11-06 18:45:27 得分 0
靠，偶笔试的时候就没做出来，被鄙视了。
随便回楼上某位的话，偶是中大的，认识的同学有2个当场拿到offer了，有1个挂过科的说1个月给通知。
Top
77 楼shareyao（）回复于 2006-11-06 19:39:28 得分 0
全排列,
递归解吧.Top
78 楼delphijava（(好之者不如乐之者)）回复于 2006-11-06 19:46:42 得分 0
那个讯雷？ 老是跳出个广告的画面 ， 烦死了 ， 那天我用录像软件录点东西， 时间比较长，
放在家里就出去了 ，回来一看 都是录了那个 讯雷的 弹出广告 。Top