9月13日星期一

题目一：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

题目描述：

输入一个int型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。保证输入的整数最后一位不是0。

程序分析

待补充

输入描述:

输入一个int型整数

输出描述：

按照从右向左的阅读顺序，返回一个不含重复数字的新的整数

示例：

输入
9876673
输出
37689

题目解析：

#include <stdio.h>
int main()
{
    int n,m=0;
    scanf("%d",&n);
    int a[10]={0};
    while(n){
        if(a[n%10]==0)
        {
            a[n%10]++;
            m=m*10+n%10;
        }
        n/=10;
    }
    printf("%d",m);
    return 0;
}

题目二：输入一个int型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。保证输入的整数最后一位不是0。

题目描述：

有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

程序分析

可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。

输入描述:

输出描述：

输出不重复的三位数

示例：

1,2,3
1,2,4
1,3,2
1,3,4
1,4,2
1,4,3
2,1,3
2,1,4
2,3,1
2,3,4
2,4,1
2,4,3
3,1,2
3,1,4
3,2,1
3,2,4
3,4,1
3,4,2
4,1,2
4,1,3
4,2,1
4,2,3
4,3,1
4,3,2

题目解析：

方法一：容易想到，但是浪费了CPU的资源，执行很多不必要的循环

#include<stdio.h>
 
int main()
{
    int i,j,k;
    printf("\n");
    for(i=1;i<5;i++) { // 以下为三重循环
        for(j=1;j<5;j++) {
            for (k=1;k<5;k++) { // 确保i、j、k三位互不相同
                if (i!=k&&i!=j&&j!=k) { 
                    printf("%d,%d,%d\n",i,j,k);
                }
            }
        }
    }
}

方法二：尽量减少不必要的循环，做了如下的小优化。

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t i; // 百位
    uint32_t j; // 十位
    uint32_t k; // 个位
    
    for (i=1; i<5; i++) {
        for (j=1; j<5; j++) {
            // 百位与十位重复
            // 跳过当前十位
            if (j==i) {
                continue;
            }
            
            for (k=1; k<5; k++) {
                // 个位与百位或十位重复
                // 跳过当前个位
                if (k==j || k==i) {
                    continue;
                }
                
                printf("%u,%u,%u\n", i, j, k);
            }
        }
    }
}
	
	```

方法三：深搜法(DFS)写此题，采用嵌套函数，可以不用写多个for循环。如果遇到需要很多个for循环的情况可以采用这种方案。

#include <stdio.h>
#include <stdlib.h>

int  b[4],arr[4];//定义两个数组用来类比
int Count=0;//计数器
void DFS(int step){
    if(step==5){
        if(arr[1]!=arr[2]&& arr[1]!=arr[3]&&arr[2]!=arr[3]){//判断哪些符合条件
            Count++;
            printf("%d%d%d\n",arr[1],arr[2],arr[3]);//输出可用排列
        }
        return ;
    }

    for(int i=1;i<=4;i++){
        if(b[i]==0){
            arr[step]=i;
            b[i]=1;//排除重复
            DFS(step+1);//自己调用自己
            b[i]=0;
        }
    }
    return ;
}

int main(void)
{
    DFS(1);
    printf("共有%d种",Count);
    return 0;
}