- //
- // main.c
- // 两个穷举方案性能对比
- //
- // Created by 颜风 on 14-4-23.
- // Copyright (c) 2014年 天启. All rights reserved.
- //
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- #include <stdlib.h>
- #include <time.h>
- //------------------函数的声明--------------
- /*穷举由给定选项组成的指定位数的所有不重复的密码组合.
- *函数核心思想在于在函数的递归调用.
- *options char* 指定密码可选项
- *opt_length unsigned 可选项总个数
- *digits unsigned 密码位数
- *pwds char** 一个用于存储生成的密码的二维数组.函数调用者需要保证它有合适的长度和宽度.
- */
- void exhaust_pwd(char* options, unsigned opt_length,unsigned digits, char** pwds);
- /*穷举由给定选项组成的指定位数的所有不重复的密码组合.
- *函数核心思想在于使用递增而不是函数的递归,以提高执行效率,一定条件下
- *options char* 指定密码可选项
- *opt_length unsigned 可选项总个数
- *digits unsigned 密码位数
- *pwds char** 一个用于存储生成的密码的二维数组.函数调用者需要保证它有合适的长度和宽度.
- */
- void exhaust_pwd_pi(char* option, unsigned opt_length,unsigned digit, char** pwds);
- //------------------函数的定义--------------
- /*穷举由给定选项组成的指定位数的所有不重复的密码组合.
- *函数核心思想在于使用递增而不是函数的递归,以提高执行效率
- *本质上是在模仿数字的进位操作
- *options char* 指定密码可选项
- *opt_length unsigned 可选项总个数
- *digits unsigned 密码位数
- *pwds char** 一个用于存储生成的密码的二维数组.函数调用者需要保证它有合适的长度和宽度.
- */
- void exhaust_pwd(char* options, unsigned opt_length, unsigned digits,char** pwds)
- {
- //调用深度
- static unsigned depth = 1;
- //计数,统计有效密码组合的总个数.
- static unsigned count = 0;
- for (int i = 1; i <= opt_length; i++) {
- //是否是密码的最后一位?
- if (depth == digits) {
- //把密码组合复制存储到pwds
- //仅最后一位不同,即最后一位需要单独设定
- for (int k=1; k < digits; k++) {
- pwds[count][k-1] = pwds[0][k-1];
- }
- pwds[count][depth-1] = options[i-1];
- //pwds存储的有效密码总个数加1.
- count++;
- continue;
- }else{
- //由于pwds的第一个密码组合是既定的,故暂时使用pwds[0]作为临时字符数组存储各个密码组合
- pwds[0][depth-1] = options[i-1];
- //遍历深度自增1
- depth++;
- exhaust_pwd(options, opt_length, digits, pwds);
- }
- }
- //判断是否穷举所有有效组合.
- if (count == pow(opt_length, digits)) {
- //正确设定pwds[0];
- for (int i = 1; i <= digits; i++) {
- pwds[0][i-1] = options[0];
- }
- }else{
- // 未穷巨额所有有效密码组合,则返回上层,继续执行
- depth--;
- }
- return;
- }
- // ---------------------------------------
- /*穷举由给定选项组成的指定位数的所有不重复的密码组合.
- *函数核心思想在于在函数的递归调用.
- *本质上是在模仿数字的进位操作
- *options char* 指定密码可选项
- *opt_length unsigned 可选项总个数
- *digits unsigned 密码位数
- *pwds pwds 一个用于存储生成的密码的二维数组.函数调用者需要保证它有合适的长度和宽度.
- */
- void exhaust_pwd_pi(char* option,unsigned opt_length,unsigned digit, char** pwds)
- {
- //注意:第一行代码为整个函数的核心,受此问题的递归方案的启发而为之!
- //记录各密码位的状态,即此密码位哪一个密码选项正在被使用;
- //初始均位0,即此密码位正使用第一个密码选项.
- int* state = (int*)malloc(sizeof(int)*digit);
- //单独处理密码位数为1的情况
- if (digit == 1) {
- for (int i = 0,count = 0; i < opt_length; i++)
- {
- //调整
- state[digit-1] = i;
- //将密码存储到pwds中
- for (int j = 0; j < digit; j++)
- {
- pwds[count][j] = option[state[j]];
- }
- //pwds中存储的密码总数加一
- count ++;
- }
- //释放内存
- free(state);
- return;
- }
- for (int count = 0; state[0] < opt_length; )
- {
- //下面这个循环对且仅会对最后一个密码位适用
- //也仅在对最后一个密码位操作时,才能得到一组完整地密码.
- for (int i = 0; i < opt_length; i++)
- {
- //调整
- state[digit-1] = i;
- //将密码存储到pwds中
- for (int j = 0; j < digit; j++)
- {
- pwds[count][j] = option[state[j]];
- }
- //pwds中存储的密码总数加一
- count ++;
- }
- //逢opt_length进一,和进制很类似.
- for (int i = 0; i < digit; i++)
- {//此处的i可理解位当前密码位与最后一位密码位的距离
- //向前一位进一
- state[digit-1-i] ++;
- //本位置为0
- state[digit-i] = 0;
- //是否有必要继续进位?
- if (state[digit-1-i] < opt_length)
- {
- break;
- }
- //是否已经是最高位?
- if (digit-1-i == 0)
- {
- break;
- }
- }
- }
- //释放内存
- free(state);
- }
- int main(int argc, const char * argv[])
- {
- //-------------测试----------------
- char options[22] ={'a','b','c','d','e',
- 'f','A','B','C','D','E','F','0','1',
- '2','3','4','5','6','7','8','9'};
- int digit = 5;//位数
- int opt_length = (int)strlen(options);//可选项数目
- printf("对于有%d个密码可选项,位数为%d的密码组合的穷举\\n",opt_length ,digit);
- //动态内存分配:定义一个行列都是动态的二维数组,用于存储所有的密码组合
- char **pwds = (char**)malloc(sizeof(char*)*pow(opt_length, digit));
- for (int i = 1; i <= pow(opt_length, digit); i++)
- pwds[i-1] = (char*)malloc(sizeof(char)*digit);
- //函数调用
- //效率比较
- //计算递归版本的密码穷举函数的时间消耗
- clock_t start_1, end_1;
- start_1 = clock();
- exhaust_pwd(options, opt_length, digit, pwds);
- end_1 = clock();
- double time_1 = (double)(end_1 - start_1) / CLOCKS_PER_SEC;
- printf("递归穷举,耗时:%lf秒\\n", time_1);
- //计算递增版本的密码穷举函数的时间消耗
- clock_t start_2, end_2;
- start_2 = clock();
- exhaust_pwd_pi(options, opt_length, digit, pwds);
- end_2 = clock();
- double time_2 = (double)(end_2 - start_2) / CLOCKS_PER_SEC;
- printf("递增穷举,耗时:%lf秒\\n", time_2);
- //手动释放pwds分配的内存
- for (int i = 1; i < pow(opt_length, digit); i++){
- free(pwds[i-1]);
- }
- free(pwds);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0810201410525.html
来源: http://www.codesnippet.cn/detail/0810201410525.html