数据结构（一）递归、中位数

1、从键盘输入求2的n次方

代码:

/*编写程序，求2的n次方 （mod 5） 
n为正整数，由用户输入，
对应每个输入，输出一个整数， 求2的n次方 （mod 5）的结果
*/ 
#include<iostream>
using namespace std; 
int main()
{
   int n;
   cin>>n;//scanf("%d",&n);
   int ans=1;
      for(int i=0;i<n;i++)
            ans=ans*2;
             cout<<ans<<endl;//printf("%d\n".ans);
       return 0;
}

运行:

2、二进制表示1的个数-1-递归

代码:

/*输入一个整数，求该整数的二进制表达中有多少个1
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
*/
#include<iostream>
using namespace std;
int test(int n) 
{ 
    int count=0; 
    while(n != 0)//循环递归 
	{ 
        if(n%2 ==1) //判断n能否整除2 
            count++; //若不能整除则记1的个数 ++
        n /= 2; //除以2后的数 
    } 
    return count; 
}
int main() 
{
    int n;
    cin>>n; 
    cout<<test(n)<<endl;
	
	return 0;
}

运行:

3、求解字谜游戏问题

代码:

#include <iostream>
#include <string>
#include <vector>
#include <Windows.h> 
using namespace std;
const int MaxLen = 4;
struct offsets
{
	int x;
	int y;
};
struct Index_of_FirstLetter
{
	int x;
	int y;
};
offsets move[8] = {	
	-1 ,  0 ,
	-1 ,  1 ,
 	0 ,  1 ,
 	1 ,  1 ,
 	1 ,  0 ,
 	1 , -1 ,
 	0 , -1 ,
	-1 , -1 
};
char Graph[MaxLen][MaxLen] = 
{
	't' , 'h' , 'i' , 's',
	'w' , 'a' , 't' , 's',
	'o' , 'a' , 'h' , 'g',
	'f' , 'g' , 'd' , 't'
};
bool test(string str , int t_rows , int t_cols , int d)	 
{
	str.erase(0 , 1);
	while(str != "")
	{
		t_rows = t_rows + move[d].x;
		t_cols = t_cols + move[d].y;
		if(Graph[t_rows][t_cols] != str[0])
		{
			return 0;
		}
		str.erase(0 , 1);
	}
	return 1;
}
void find(string str , int rows , int cols)	 
{
	str.erase(0 , 1);	
	int t_rows;
	int t_cols;
	for(int d = 0; d <= 7; d++)	
	{
		t_rows = rows + move[d].x;
		t_cols = cols + move[d].y;
		if(Graph[t_rows][t_cols] == str[0] && test(str , t_rows , t_cols , d))
		{	
			system("pause");
			exit(1);			
		}
	}
	system("pause");
	exit(1);
}

int main()
{
	string str;
	cout << "单词：" ;  
	cin >> str;
	char FirstLetter = str[0];
	vector<Index_of_FirstLetter> vs;	 

	if(str.length() > MaxLen)	
	{
		cerr << "出错" << endl;
		return 0;
	}
	
	
	for(int i = 0; i < MaxLen; i++)
	{
		for(int j = 0; j < MaxLen; j++)
		{
			if(Graph[i][j] == FirstLetter)		
			{
				vs.push_back(Index_of_FirstLetter{i , j});
			}
		}
	}
	
	for(int i = 0; i < vs.size(); i++)		
	{
		find(str , (vs[i]).x , (vs[i]).y);
	}
	return 0;
}

运行://

 

4、中位数

代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <Windows.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
void generate_vector(vector<int>& , const long long& );	
int main()
{
	vector <int> array;	
	array.reserve(1000000); 
	long long n;
	clock_t starttime , endtime;//clock()是C/C++中的计时函数，而与其相关的数据类型是clock_t。
//在MSDN中，查得对clock函数定义如下：clock_t clock(void)
	cout << "请输入数据个数：" << endl;
	cin >> n;
	generate_vector(array , n);	//初始化vector	
	starttime = clock();		
	sort(array.begin(), array.end());
	cout << (array.size() % 2 == 0 ? (array[array.size() / 2] + array[array.size() / 2 - 1]) / 2 : array[array.size() / 2]) << endl;
	endtime = clock();
	cout << "Running time:" << double(endtime - starttime)/CLOCKS_PER_SEC<<endl;
	system("pause"); 
	return 0;
}
void generate_vector(vector<int>& array , const long long& n)
{
	for(int i = 0; i < n;i++ )  
	{
		array.push_back(rand());//C++产生随机数组
		srand((unsigned)time(NULL));
/*srand函数是随机数发生器的初始化函数。原型:void srand(unsigned seed);
用法:它初始化随机种子，会提供一个种子，这个种子会对应一个随机数，如果使用相同的种子后面的rand()函数会出现一样的随机数
不过为了防止随机数每次重复，常常使用系统时间来初始化，即使用time函数来获得系统时间
当srand()的参数值固定的时候，rand()获得的数也是固定的，所以一般srand的参数用time(NULL)，
因为系统的时间一直在变，所以rand()获得的数，也就一直在变，相当于是随机数了。
只要用户或第三方不设置随机种子，那么在默认情况下随机种子来自系统时钟。
*/
	} 
}

运行:

5、字符串全排列-递归

代码:

/*
方法一:求字符串a{n}的全排列，可以分解为求a{n - 1}的全排列，对于a{n - 1}的每一个全排列结果，
只要将a[n]插入到a{n - 1}序列的n个位置中，即可得到a{n}的全排列结果。
例如：求abc的全排列，可以先求ab的全排列，再将c插入到第0,1,2位即可得到abc的全排列，
而对于ab的全排列，可以先求a的全排列，再将b插入到第0,1位即可得到ab全排列结果，
因为a是单个字符，它的全排列结果只有一个：a，所以递归开始返回，层层向上，得到abc的全排列的解。
总结：这是基于插入操作的算法！
方法二:用123来示例下。123的全排列有123、132、213、231、312、321这六种。
首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。
然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。
因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。
*/
#include<iostream>  
using namespace std;  
#include<assert.h>  //assert宏的原型定义在<assert.h>中，其作用是如果它的条件返回错误，则终止程序执行
  
int Permutation(char* pStr, char* pBegin)  
{  
    assert(pStr && pBegin);  
    if(*pBegin == '\0')  
        cout<<pStr<<endl;//printf("%s\n",pStr);  
    else  
    {  
        for(char* pCh = pBegin; *pCh != '\0'; pCh++)  
        {  
            swap(*pBegin,*pCh);  
            Permutation(pStr, pBegin+1);  
            swap(*pBegin,*pCh);  
        }  
    }  
}  
int main(void)  
{  
    char str[] = "abc";  
    Permutation(str,str);  
    return 0;  
}  

运行: