/*输出1,2,3,4,5全排列且3和4不相邻的所有数*/
#include <stdio.h>
main()
{
int i,j,k,m,n,p,q,counter=0;
int num[5]={0};
for(i=1;i<=5;i++)
for(j=1;j<=5;j++)
for(k=1;k<=5;k++)
for(m=1;m<=5;m++)
for(n=1;n<=5;n++)
{
num[0]=i;
if(j!=i)
{
num[1]=j;
if(k!=i&&k!=j)
{
num[2]=k;
if(m!=i&&m!=j&&m!=k)
{
num[3]=m;
if(n!=i&&n!=j&&n!=k&&n!=m) /*输出所有全排列的数 */
{
num[4]=n;
if(num[0]==3&&num[1]!=4) /*筛选1 */
{
for(q=0;q<5;q++)
printf("%d",num[q]);
printf("\n");
counter++;
}

for(p=1;p<4;p++)
{
if(num[p]==3&&num[p+1]!=4&&num[p-1]!=4)/*筛选2*/
{
for(q=0;q<5;q++)
printf("%d",num[q]);
printf("\n");
counter++;
}
}

if(num[4]==3&&num[3]!=4)/*筛选3*/
{
for(q=0;q<5;q++)
printf("%d",num[q]);
printf("\n");
counter++;
}

}
}
}
}
}
printf("There are %d numbers!\n",counter);
}

从理论上算,共有 5!-2!*4!=72 个数满足题意,与程序输出结果相一致.

楼上的算法复杂度太高了，光一个全排列的复杂度就是5的6次方
这个数字太大了吧……
有没有算法复杂度低点的？

可以考虑用递归

/*看看我的是否可以*/

#include<stdio.h>
int cont=1 ;
void test(int str[],int n)
{
int i,j,k,l,m,a=0,b[5];
for(i=0;i<n;i++)
{
m=0 ;
for(j=i;j<n;j++)
if(str[i]>str[j])b[m++]=str[j];
}
i=0 ;
while(i<n&&str[i]!=3)
{
i++;
}
if((i>0&&str[i-1]==4)||(i<n-1&&str[i+1]==4))
{
a=1 ;
}
if(a==0)
{
printf(" 第%2d种情况:",cont++);
for(i=0;i<n;i++)
printf("%d",str[i]);
printf("\n");
}
}
void perm(int str[],int k,int n)
{
int i,temp ;
if(k==n-1)
{
test(str,n);
}

else
{
for(i=k;i<n;i++)
{
temp=str[k];
str[k]=str[i];
str[i]=temp ;
perm(str,k+1,n);
temp=str[i];
str[i]=str[k];
str[k]=temp ;
}
}
}
int main()
{
int str[5],n,i ;
for(i=0;i<5;i++)str[i]=i+1 ;
printf("各种情况:\n");
perm(str,0,5);
printf("\n");
return(0);
}

14楼的思路很好,不错不错

11楼那个效率太低了

14楼可以把注释加上吗？
看着有些费劲……