全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了,因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处,欢迎大家指出。
首先来看看题目是如何要求的(百度迅雷校招笔试题)。
用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba
一.全排列的递归实现
为方便起见,用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后,递归的代码就很容易写出来了:
// AllRange.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
//全排列的递归实现
#include <stdio.h>
#include <string.h>
#include <iostream>
void Swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{
if (k == m)
{
static int s_i = 1;
printf(" 第%3d个排列\t%s\n", s_i++, pszStr);
}
else
{
for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
{
Swap(pszStr + k, pszStr + i);
AllRange(pszStr, k + 1, m);
Swap(pszStr + k, pszStr + i);
}
}
}
void Foo(char *pszStr)
{
AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
printf(" 全排列的递归实现\n");
printf(" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");
char szTextStr[] = "123";
printf("%s的全排列如下:\n", szTextStr);
Foo(szTextStr);
system("pause");
return 0;
}
分享到:
相关推荐
迅雷笔试题(全套)迅雷笔试题(全套)迅雷笔试题(全套)
百度历年笔试题百度历年笔试题百度历年笔试题百度历年笔试题
百度笔试题 百度 笔试题 百度 笔试题
百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题
百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全
迅雷笔试题,对找工作的朋友有帮助,可以一看
迅雷笔试题面经整理迅雷笔试题面经整理迅雷笔试题面经整理迅雷笔试题面经整理
百度校招笔试题.doc
百度笔试题,一套完整的百度笔试题,有要应聘百度的兄弟不要错过。
2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度校园招聘笔试题.docx2010百度...
一套百度的笔试题,蓝色部分为参考答案 (本资源来自互联网)
百度历年笔试试题汇总 技术类笔试试题 算法 数据结构等
百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘笔试题及答案-未知年份及岗位(1).docx百度校园招聘...
百度校招笔试题.docx百度校招笔试题.docx百度校招笔试题.docx百度校招笔试题.docx百度校招笔试题.docx百度校招笔试题.docx百度校招笔试题.docx百度校招笔试题.docx
百度公司两年来的笔试题,快来看啊
想得到迅雷的offer,请知己知彼~~~嘿嘿嘿嘿嘿嘿嘿嘿嘿嘿
12年5月份的百度前端笔试题,看你的距离在哪里。
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
2011百度校园招聘笔试题 C++类-附原创答案.docx2011百度校园招聘笔试题 C++类-附原创答案.docx2011百度校园招聘笔试题 C++类-附原创答案.docx2011百度校园招聘笔试题 C++类-附原创答案.docx2011百度校园招聘笔试题 ...