欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构(一)递归、中位数

程序员文章站 2022-03-31 10:30:03
...

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;  
}  

运行:

数据结构(一)递归、中位数

 

 

相关标签: 递归