c语言代码题 有重复全排列 [2*] 输出N个数的有重复全排列 Input 一个整数N 1<=N<=5 Output 输出n个数的有重复全排列 Sample Input 3 Sample Output 111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333

这是一个比较经典的回溯算法问题，可以用递归来实现。下面是一个 C 语言的实现：

#include <stdio.h>

int n;
int nums[6];

void dfs(int index) {
    if (index > n) {
        for (int i = 1; i <= n; i++) {
            printf("%d", nums[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        nums[index] = i;
        dfs(index + 1);
    }
}

int main() {
    scanf("%d", &n);
    dfs(1);
    return 0;
}

输入样例：

3

输出样例：

111
112
113
121
122
123
131
132
133
211
212
213
221
222
223
231
232
233
311
312
313
321
322
323
331
332
333

相关问题

用c语言写设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。

在C语言中，我们可以使用递归的方式来编写一个全排列的算法。这里我们先定义一个结构体来存储输入的一系列元素，然后创建一个函数`permute`来处理这个任务。对于整数或字符的排列，基本思想是每次从剩余未排列的元素中选择一个放到当前位置，然后递归地对剩下的元素进行排列。

#include <stdio.h>
#include <string.h>

typedef void (*permutation_func)(void *, int);

// 用于存储元素的结构体
struct Item {
    int value;
    char ch; // 如果是字符类型，可以替换为char
};

// 遍历数组并打印全排列
static void print_permutation(struct Item *arr, permutation_func permute, void *context) {
    if (permute(arr, context)) { // 如果递归结束，打印并回溯
        for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i) {
            printf("%d ", arr[i].value); // 或者 printf("%c ", arr[i].ch);
        }
        printf("\n");
    } else {
        // 移除当前元素并继续递归
        for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i) {
            if (arr[i].value != context) { // 或者 arr[i].ch != context
                swap(&arr[0], &arr[i]); // 交换位置
                permute(arr, arr[0].value); // 递归调用，传递新的元素作为上下文
                swap(&arr[0], &arr[i]); // 撤销交换，恢复原始状态
            }
        }
    }
}

// 递归函数，返回值表示是否到达排列结束
static int permute_helper(struct Item *arr, int last_used) {
    if (last_used == sizeof(arr)/sizeof(arr[0]) - 1) return true; // 所有元素都已使用，递归结束

    // 尝试将下一个可用元素放在当前位置
    for (int i = last_used + 1; i < sizeof(arr)/sizeof(arr[0]); ++i) {
        swap(&arr[last_used], &arr[i]);
        if (!permute_helper(arr, i+1)) { // 如果无法再放置下一个元素，则撤回操作
            swap(&arr[last_used], &arr[i]); // 撤销交换
        }
    }

    return false; // 还有未使用的元素，未到排列结束
}

void generate_permutations(char* input, size_t length) {
    struct Item elements[length];
    for (size_t i = 0; i < length; ++i) {
        elements[i].value = input[i] - '0'; // 如果输入是数字
        // 或者 elements[i].ch = input[i]; // 如果输入是字符
    }
    
    permutation_func permute = permute_helper;
    print_permutation(elements, permute, 0);
}

int main() {
    char input[] = "1234";
    generate_permutations(input, strlen(input));
    return 0;
}

适合新手理解的C语言:设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。

在C语言中，设计一个递归算法生成n个元素的全排列可以利用排列组合的知识和递归思想。这里有一个简单的例子，它适用于字符串（字符数组），因为全排列的概念同样适用于字符。假设我们有一个字符数组`arr[]`，其长度为`n`。

下面是一个基本的递归函数`generate_permutations()`，用于生成所有可能的排列：

#include <stdio.h>
#include <string.h>

void swap(char *x, char *y) {
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void generate_permutations(char arr[], int n, int index) {
    if (index == n) {
        // 当索引等于n时，已经生成了一个完整的排列，打印出来
        for (int i = 0; i < n; i++) {
            printf("%c", arr[i]);
        }
        printf("\n");
    } else {
        // 对于每个当前位置，尝试将其与剩余位置交换，然后递归处理剩余部分
        for (int i = index; i < n; i++) {
            swap(&arr[index], &arr[i]); // 交换当前位和下一位
            generate_permutations(arr, n, index + 1); // 递归调用处理剩余
            swap(&arr[index], &arr[i]); // 撤销交换，回溯到上一步
        }
    }
}

int main() {
    char input[100];
    printf("Enter the string to permute: ");
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = '\0'; // Remove newline character

    int n = strlen(input);
    generate_permutations(input, n, 0);

    return 0;
}

这个程序首先读取用户输入的字符串，然后计算它的长度。`generate_permutations()`函数通过递归调用自身以及`swap()`函数，实现了从当前位置开始的每个元素与其后面的所有元素的交换，生成所有可能的排列。当索引达到字符串长度时，就找到了一个完整排列并打印出来。