若干经典基础算法题目练习

阅读量：5836 次

发布时间：2019-06-18

本文共 33694 字，大约阅读时间需要 112 分钟。

练习1，推断是否为素数：

// ConsoleAppIsPrime1.cpp : 定义控制台应用程序的入口点。

// /* *函数功能：推断一个输入的数是否为素数 *函数原形：bool Prime( int x ) *參数：int x：将要推断的数 *返回值：bool型变量，推断是否是素数 *备注：须要包括头文件<math.h> *日期：2014/11/25 *原创：否 *作者：EbowTang *Email：tangyibiao520@163.com */ #include "stdafx.h" #include "math.h" #include "iostream" using namespace std; bool Prime( int x ); int _tmain(int argc, _TCHAR* argv[]) { bool flag; int a; while (true) { cout<<"Please enter a number:"; cin>>a; flag=Prime(a); if (flag==true) cout<<"Prime!!!"<<endl; else cout<<"Not Prime!"; } system("pasue"); return 0; } /*原理：将输入的x与2到sqrt（x）整除一遍，若当中随意一个能整除则x不是素数*/ bool Prime( int x ) { x=abs( x ); if ( x < 1 ) return false; for (int i = 2; i <= int( sqrt( float( x ))) ; i++ ) { if ( x % i==0 )//一旦能够整除立刻返回他不是素数 return false; } return true; }

练习2，指定范围内的素数：

// ConsoleAppIsPrime.cpp : 定义控制台应用程序的入口点。///**函数功能：推断指定范围内素数个数*函数原形：int Primes( int n ,int m )*參数：int n：请输入想要确认的素数范围下限int m：请输入想要确认的素数范围上限*返回值：n到m范围内素数的个数*备注：*日期：2014/11/25*原创：是*作者：EbowTang*Email：tangyibiao520@163.com*/#include "stdafx.h"#include "iostream"#include "math.h"using namespace std;int Primes( int n ,int m );bool Prime( int x );int _tmain(int argc, _TCHAR* argv[]){	int countprimes=0;	int a=0;	int b=0; 		while (true)	{		cout<<"请输入想要确认的素数范围上限：";		cin>> a ;		cout<<"请输入想要确认的素数范围下限：";		cin>> b;		countprimes=Primes(a,b);		cout<<"在 "<< a <<"到 "<< b <<"之间的素数个数为: "<< countprimes<

练习3，某整数是否为2的次幂：

/**函数功能：推断一个整数是否为2的次幂*函数原形：bool IsTwoN(int n);*參数：int n，要推断的整数*返回值：bool型变量，表征是与否*时间复杂度：O(1)*备注：无*日期：2014/11/23*原创：否*作者：EbowTang*Email：tangyibiao520@163.com*/#include "stdafx.h"#include "iostream"#include "math.h"using namespace std;bool IsTwoN(int n);int _tmain(int argc, _TCHAR* argv[]){		while(1)	{		bool flag;		int m;		cout<<"请输入一个整数："<
     
      >m;		flag=IsTwoN(m);		if (flag==true)			cout<
      
       <<"是2的次幂,恭喜你！

"<<endl<<endl; else cout<<m<<"不是2的次幂"<<endl<<endl; } return 0; } bool IsTwoN(int n) { //若是，必然与其自身减1后的数相“与”为假，比方8,1000&0111=0000, //if(n>0&&((n&(n-1))==0))/*第一种方法*/ //假设n==2的log以2为底数的n对数的pow函数后，则是 if (n==pow(2,(int)(log10(n)/log10(2.))))/*另外一种方法*/ return true; else return false; }

练习4。整数的二进制数中1的个数：

/**函数功能：求取整数相应二进制数中1的个数*函数原形：int Count(int z);*參数：int z，要计算的整数*返回值：返回整数相应二进制数中1的个数*时间复杂度：O(1)*备注：无*日期：2014/11/23*原创：否*作者：EbowTang*Email：tangyibiao520@163.com*/#include "stdafx.h"#include "iostream"using namespace std;int Count(int z);int main(){	int number;	int z;	char asn='n';	do 	{	cout<<"请输入一个整数:"<
     
      >z;	number=Count(z);	cout<<"该整数相应二进制数1的个数为:"<
      
       >asn;	} while (asn=='y');	return 0;}int Count(int v){	int num=0;	while (v)	{		//第一种算法：复杂度较低		//	num+=v & 0x01;		//	v >>=1;		//另外一种算法：		//	v&=(v-1);		//	num++;		/*第三种算法：算法复杂度较高*/		if(v%2==1)			num++;		v=v/2;	}	return num;}

练习5。统计指定数据出现次数：

// ConsoleAppDigitCount.cpp : 定义控制台应用程序的入口点。///**问题描写叙述：用随机函数生成100个在100到999之间的整数，设计程序统计这些三位数中十位是各自是0-9出现次数*问题演示样例：无*函数功能：统计三位数中十位数0-9出现的次数*函数原形：void DigitCount(int num[], int count[])*參数：int num[], 欲统计的数组，int count[]存储统计结果*返回值： 无    *时间复杂度：O(n)*备注：无*日期：2014/12/31*算法描写叙述：*/#include "stdafx.h"#include "iostream"#include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAX 100using namespace std;/**函数功能：生成100到999的随机整数数*函数原形：void RandNumIn(int num[])*參数：int num[]。用于存储随机整数*返回值：无*/void RandNumIn(int num[]){	srand((unsigned)time(NULL));  //设置随机种子	for( int i=0; i

练习6，进制的转换：

// ConsoleAppHexadecimalTrans.cpp : 定义控制台应用程序的入口点。

// /* *问题描写叙述：将十进制转换成二进制或者八进制，16进制 *问题演示样例：输入50 2。输出110010 *函数功能： *函数原形：void HexadecimalTrans(int n, int d) *參数：int n,十进制整数 int d，进制数 *返回值：无 *时间复杂度： *备注：无 *日期：2014/11/30 *算法描写叙述： */ #include "stdafx.h" #include <iostream> using namespace std; int flag=1; void HexadecimalTrans(int n, int d) { int mod; mod=n%d; //n表示数字，d表示进制 n=n/d; while(flag && n) //辗转相除 HexadecimalTrans(n,d); switch(mod) { case 10: cout<<"A"; break; case 11: cout<<"B"; break; case 12: cout<<"C"; break; case 13: cout<<"D"; break; case 14: cout<<"E"; break; case 15: cout<<"F"; break; default: cout<<mod; //二进制和八进制均在这里输出，mod保存了辗转相除的每次结果 } flag=0; } int _tmain(int argc, _TCHAR* argv[]) { int n, d; cout<<"输入十进制数字:"<<endl; cin>>n; cout<<"请输入将要进行的进制转换（2，8,16）:"<<endl; cin>>d; HexadecimalTrans(n,d); //调用转换函数 cout<<endl; system("pause"); return 0; }

练习7，查找指定数据的位置（暴力搜索）：

// ConsoleAppSpecifiedSearch.cpp : 定义控制台应用程序的入口点。

// /* *问题描写叙述：暴力搜索遍历查找。从100个随机函数中（100-999）查找指定数字的位置 *问题演示样例： *函数功能：查找指定的数 *函数原形：int FindNum(int num[], int x) *參数：int num[]。要查找的数组, int x。要查找的数 *返回值：数字的位置 *时间复杂度：O() *备注：无 *日期：2014/7/30 *算法描写叙述： */ #include "stdafx.h" #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; #define MAX 100 /* *函数功能：产生指定的随机数 *函数原形：void RandNumIn(int num[]) *參数：int num[]，产生的随机数保存到数组num中 *返回值：无 */ void RandNumIn(int num[]) { int i; srand((unsigned)time(NULL)); //得到随机种子 for(i=0; i<MAX; i++) num[i]=100+rand()%900; //生成100--999以内的随机三位整数 } /* *函数功能：输出产生的随机数 *函数原形：void RandNumOut(int num[]) *參数：int num[]，将要输出的数组 *返回值：无 */ void RandNumOut(int num[]) { int count=0; for(int i=0; i<MAX; i++) { cout<<num[i]<<" "; count++; if(0==count%10) cout<<endl; } } /* *函数功能：查找指定的数 *函数原形：int FindNum(int num[], int x) *參数：int num[]，要查找的数组, int x，要查找的数 *返回值：数字的位置 */ int FindNum(int num[], int x) { for(int i=0; i<MAX; i++) if(x == num[i]) //遍历查找指定数字的位置 return i; return 0; } int _tmain(int argc, _TCHAR* argv[]) { int x, pos, num[MAX]; //设置存储数组 RandNumIn(num); cout<<"随机生成的数字: "<<endl; RandNumOut(num); cout<<"请输入要查找的三位整数"<<endl; cin>>x; pos=FindNum(num, x); //调用查找函数 if(pos) cout<<"太好了!"<<x<< "的位置在: "<< pos<<endl; else cout<<"抱歉!"<<x<< "并未找到! "<<endl; system("pause"); return 0; }

练习8，二分法查找指定数据位置：

// ConsoleAppSpecifiedSearch.cpp : 定义控制台应用程序的入口点。

// /* *问题描写叙述：二分法遍历查找。从100个随机函数中（100-999）查找指定数字的位置 *问题演示样例： *函数功能：二分查找法查找指定的数 *函数原形：int SpecialFindNum(int num[], int x, int low, int high) *參数： int num[]。要查找的数组, int x。要查找的数 int low, 查找的起始位置 int high，查找的末端位置 *返回值：数字的位置 *时间复杂度：O() *备注：无 *日期：2014/7/30 *算法描写叙述： */ #include "stdafx.h" #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; #define MAX 101 /* *函数功能：产生指定的随机数 *函数原形：void RandNumIn(int num[]) *參数：int num[]，产生的随机数保存到数组num中 *返回值：无 */ void RandNumIn(int num[]) { int i; srand((unsigned)time(NULL)); //得到随机种子 for(i=1; i<MAX; i++) num[i]=100+rand()%900; //生成100--999以内的随机三位整数 } /* *函数功能：输出产生的随机数 *函数原形：void RandNumOut(int num[]) *參数：int num[]。将要输出的数组 *返回值：无 */ void RandNumOut(int num[]) { int count=0; for(int i=1; i<MAX; i++) { cout<<num[i]<<" "; count++; if(0==count%10) cout<<endl; } } /* *函数功能：高速排序法 *函数原形：void QuickSort(int num[], int low, int high) *參数： int num[]。要排序的数组, int low, 查找的起始位置 int high。查找的末端位置 *返回值：无 */ void QuickSort(int num[], int low, int high) { int l, h; if(low<high) { l=low; h=high; num[0]=num[l]; while(l<h) { while(l<h && num[h]>=num[0]) h--; //利用高速排序是数据有序 num[l]=num[h]; while(l<h && num[l]<=num[0]) l++; num[h]=num[l]; } num[l]=num[0]; QuickSort(num, low, l-1); QuickSort(num, l+1, high); } } /* *函数功能：二分查找法查找指定的数 *函数原形：int SpecialFindNum(int num[], int x, int low, int high) *參数： int num[]，要查找的数组, int x，要查找的数 int low, 查找的起始位置 int high。查找的末端位置 *返回值：数字的位置 */ int SpecialFindNum(int num[], int x, int low, int high) { int mid; //中间位置 while(low<=high) { mid=(low+high)/2; /* 找到 */ if(x==num[mid]) return mid; else if(x<num[mid]) //两边的游标不停往中间移动比較 high=mid-1; else low=mid+1; } return 0; } int _tmain(int argc, _TCHAR* argv[]) { int x, pos, num[MAX]; RandNumIn(num); cout<<"排序前:"<<endl; RandNumOut(num); QuickSort(num, 1, MAX-1); cout<<"排序后："<<endl; RandNumOut(num); cout<<"请输入要查找的数："<<endl; cin>>x; pos=SpecialFindNum(num, x, 1, MAX-1); //调用查找函数 if(pos) cout<<"太好了!"<<x<< "的位置在: "<< pos<<endl; else cout<<"抱歉"<<x<< "没有找到 "<<endl; system("pause"); return 0; }

练习9。字符串中指定数据出现次数

// ConsoleAppCharCount.cpp : 定义控制台应用程序的入口点。///**问题描写叙述：设计一个程序。统计随机给出的字符串的数字的个数。字母的个数，特殊字符的个数*问题演示样例：123asd。数字3，字母3，特殊字符0*函数功能：统计字符串中的数据*函数原形：void CharCal(char *str, int count[])*參数：char *str,欲统计的字符串， int count[]，用于存储统计结果*返回值：无*时间复杂度：O()*备注：无*日期：2014/7/30*算法描写叙述：*/#include "stdafx.h"#include 
     
      #include 
      
       #define MAX 1024using namespace std;/**函数功能：统计字符串中的数据*函数原形：void CharCal(char *str, int count[])*參数：char *str,欲统计的字符串， int count[]。用于存储统计结果*返回值：无*/void CharCal(char *str, int count[]){	while(*str) 	{		if((*str>='0')&&(*str<='9'))      //统计数字型字符			count[0]++;		else if(((*str>='a')&&(*str<='z')) || ((*str>='A')&&(*str<='Z'))) //统计字符型字符			count[1]++;                   		else                      //其它特殊字符			count[2]++;		str++;//指针移动	}}/**函数功能：输出统计结果*函数原形：void CharCount( int count[])*參数： int count[]，存储统计结果的数组*返回值：无*/void CharCount( int count[]){	for(int i=0; i<3; i++)	{		switch(i)		{		case 0:			cout<<"数字："<
       
        <
        
         数字; 1->字符; 2->其它	memset(count, 0, 3*sizeof(int));      //初始化统计数组	cout<<"输入字符串: "<
         
          >str;	CharCal(str, count);//统计	CharCount(count);//输出显示	system("pause");	return 0;}

练习10，逆序输出字符串

// ConsoleAppCharTest.cpp : 定义控制台应用程序的入口点。

// /* *问题描写叙述：输入字符串。将其逆序输出 *问题演示样例：输入，asdfgh。输出hgfdsa *函数功能：逆序输出字符串的内容 *函数原形：void Reverse( char* s, int left, int right ); *參数： char *,欲逆序的字符串。 int left, 逆序的左起点 int right。逆序的右尾点 *返回值：无 *时间复杂度：O(n) *备注：无 *日期：2014/7/30 *算法描写叙述： */ #include "stdafx.h" #include<iostream> using namespace std; void Reverse( char* s, int left, int right ); int _tmain(int argc, _TCHAR* argv[]) { int len; char a[100]; while(1) { cout<<"请输入字符串a："<<endl; cin>>a; len=strlen(a); Reverse(a,0,len-1); for(int i=0;i<len;i++) cout<<a[i]; cout<<endl; } return 0; } //算法一：对字符串s在指定区间left和right之间进行逆序。递归法 void Reverse( char* s, int left, int right ) { if(left >= right) return; char t = s[left] ; s[left] = s[right] ; s[right] = t ; Reverse(s, left + 1, right - 1) ; } /* //算法二：与上面的方法没有太大差别 void Reverse( char* s, int left, int right ) { while( left < right ) { char t = s[left] ; s[left++] = s[right] ; s[right--] = t ; } }*/

练习11。字符串包括推断

// ConsoleAppCharTest.cpp : 定义控制台应用程序的入口点。

// /* *问题描写叙述：输入两个字符串，推断相互之间字符串是否包括 *问题演示样例：输入，asdfgh，输出asd。结果。包括！ *函数功能：推断两个字符串是否包括 *函数原形：bool IsContain(char *pStrA, char *pStrB); *參数： char *pStrA, 第一个字符串 char *pStrB，第二个字符串 *返回值：布尔变量 *时间复杂度：O(n) *备注：无 *日期：2014/7/30 *算法描写叙述： */ #include "stdafx.h" #include "iostream" using namespace std; bool IsContain(char *pStrA, char *pStrB); int _tmain(int argc, _TCHAR* argv[]) { char a[10],b[10]; bool flag; while(true) { cout<<"Please Enter characters A:"<<endl; cin>>a; cout<<"Please Enter characters B:"<<endl; cin>>b; flag=IsContain(a, b); if (flag==false) cout<<"Not Contain!"<<endl; else cout<<"Contain!"<<endl; } return 0; } //算法1 bool IsContain(char *pStrA, char *pStrB) { int lenA = strlen(pStrA); int lenB = strlen(pStrB); int i,j; char temp; for( i = 0; i < lenA; i++) {//直接对字符数组A进行循环移位再立刻进行字符包括推断 temp = pStrA[0]; for( j = 0; j < lenA - 1; j++) pStrA[ lenA - 1] = pStrA[j + 1]; pStrA[j] = temp; if(strncmp(pStrA, pStrB, lenB) == 0) return true; } //若果运行到最后都还没有匹配成功，则返回false if(i == lenA) return false; }/* //算法2 bool IsContain(char *pStrA, char *pStrB) { int lenp = strlen(pStrA); char *temp = (char*)malloc(2 * lenp + 1);//动态分配内存 strcpy_s(temp,2 * lenp + 1,pStrA); strcpy_s(temp + lenp, 2 * lenp + 1,pStrA); if(strstr(temp, pStrB)) return TRUE; else return FALSE; }*/

练习12，打印随意位元的格雷码序列：

比方3位的全部格雷码：

000

001

011

010

110

111

101

100

代码例如以下：

// ConsoleAppGrayCode.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "iostream"using namespace std;bool GrayCode(int nBits);int changeBit(int a);int _tmain(int argc, _TCHAR* argv[]){	int nBits=0;	cout<<"请输入位元长度:"<
      
       >nBits;	GrayCode(nBits);	system("pause");	return 0;}bool GrayCode(int nBits){	bool flag=true;	do 	{		if (nBits<0)		{			cout<<"你的输入有误，请又一次输入:"<
       
        >nBits;		}else		{			flag=false;		}	} while (flag);	int *pGray=new int[nBits];	for (int i=0;i
        
         =0;j--)			{				if (pGray[j]==1)				{					pGray[j-1]=changeBit(pGray[j-1]);					break;				}			}			for (int i=0;i

还有一份可參考代码：

#include 
      
       using namespace std;#define CHANGE_BIT(a) a=((a=='0')? '1':'0')             //定义宏实现改变位元值#define NEXT_BIT(x) x=(1-(x))                         //设定奇数项或偶数项/***************构建n位元的格雷码***************/void findGrayCode(int n){	if (n <=0)	{		cout<<"输入超出有效范围"<
       
        =0;i--)                      //输出改格雷码		{			cout<
        
         >n;	cout<
         
          <<"位元的格雷码为："<

练习14，约舍夫出局

N个人围成一圈，从第一个開始报数，第M个将出局，最后剩下一个，其余人都将出局。

比如N=6。M=5。被出局的顺序是：5，4，6，2，3。1。

（1）CircleList.h的代码例如以下：

#include "stdafx.h"#include "iostream"using namespace std;template
      
       class LinkList;template
       
        class LinkNode{public:	LinkNode()	{		next = NULL;		data = 0;	}	//函数參数表中的形參同意有默认值，可是带默认值的參数须要放后面	LinkNode(DataType item)    	{		next = NULL;		data = item;	}	friend class LinkList
        
         ;private:	DataType data;	LinkNode
         
           *next;};/* 带头结点的单链表定义 */template
          
           class LinkList{public:	//无參数的构造函数	LinkList(int size)	{		head = new LinkNode
           
            ;//头结点 maxSize=size; nLength=0; } //析构函数 ~LinkList() { } //获取链表长度 int Length() const { return nLength; } //定位指定的位置，返回该位置上的结点指针 LinkNode
            
             * Locate(int pos); //在指定位置pos插入值为item的结点。失败返回false bool Insert(DataType item, int pos); //打印链表 void Print() const; //创建一个链表环 void CreatCircle(); //推断是否纯在单链表环 bool IsCircle(); //数数移动 bool CountMove( int nStep=0 ,int i=0 ); private: LinkNode
             
               *head; int maxSize; int nLength;};/* 返回链表中第pos个元素的地址。假设pos<0或pos超出链表最大个数返回NULL */template
              
               LinkNode
               
                * LinkList
                
                 ::Locate(int pos){ LinkNode
                 
                   *p = head;//head和p指向共同的内容,头结点无数据。仅仅是个指针 if (pos < 0) { cerr<<"位置參数有错误"<
                  
                   next; i++; } return p;}template
                   
                    bool LinkList
                    
                     ::Insert(DataType item, int pos){ if (Length() >= maxSize) { cout<<"错误：链表已满"<
                     
                       *p = Locate(pos); LinkNode
                      
                        *newNode = new LinkNode
                       
                        (item);//创建新节点 if (NULL == newNode) { cerr << "分配内存失败!" << endl; exit(1); } newNode->next = p->next; p->next = newNode; nLength++; return true;}template
                        
                         void LinkList
                         
                          ::Print() const{ int count = 0; LinkNode
                          
                            *p = head; while (NULL != p->next) { p = p->next; std::cout << p->data << " "; if (++count % 15 == 0) //每隔十个元素。换行打印 cout << std::endl; }}//创建一个链表环template
                           
                            void LinkList
                            
                             :: CreatCircle(){ int nLen=Length(); int nLen1=1; LinkNode
                             
                               *ptail=Locate(nLen); LinkNode
                              
                                *pcirStart=Locate(nLen1); ptail->next=pcirStart;}//是否纯在链表环?template
                               
                                bool LinkList
                                
                                 ::IsCircle(){ if ( head ==NULL) { cerr<<"空链表"<
                                 
                                   *pFast,*pSlow; pSlow=head; pFast=head; while(pFast!=NULL&&pFast->next!=NULL) { pFast=pFast->next->next; pSlow=pSlow->next; if (pSlow==pFast) { return true; break; } } return false;}
                                  template
                                   
                                    bool LinkList
                                    
                                     ::CountMove( int nStep,int k)//指定出局人数{	if (  k > Length() )	{		cerr<<"写你麻痹，滚回去检查!"<
                                     
                                       *pCurr=NULL,*pPrev=NULL;  	int i = 0;    // 计数  	int n=0;	pCurr = pPrev = head;  	while( n < k )  	{  		if (i == nStep)  		{  			// 踢出环  			cout<<"第 "<
                                      
                                       <<" 次出局"<<":  ";			cout<<"当前出局人编号"<
                                       
                                        data<
                                        
                                         next = pCurr->next; delete pCurr; pCurr = pPrev->next; i = 1; n++; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 cout<<"第 "<
                                         
                                          <<" 次出局"<<": "; cout<<"最后的出局人为："<
                                          
                                           data<<" "; // 显示出圈循序 delete pCurr; //最后一个节点删除后的“擦屁股”处理 pCurr=NULL; head->next=head; n++; break; } i++; } return true;}

(2)主測试代码：

// Win32AppCircleOut.cpp : 定义控制台应用程序的入口点。

// #include "stdafx.h" #include "CircleList.h" using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int nlen=10; LinkList<int> s(nlen); for (int i=0;i<nlen;i++) { s.Insert(i+1,i); } s.CreatCircle(); if (s.IsCircle()) { cout<<"环已经生成，能够開始了。"<<endl; } s.CountMove(3,10);//数到3出局，记录前30个人的出局情况 system("pause"); return 0; }

练习15，汉诺塔递归

汉诺塔递归问题：

// ConsoleAppHanoi.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "iostream"using namespace std;int Hanoicount=0;bool HanoiMove(int n,char a,char b,char c);//将n个盘从a借助b移动到cint _tmain(int argc, _TCHAR* argv[]){	HanoiMove(5,'A','B','C');	cout<<"共进行了："<
      
       <<"次"<
       
        "<
        
         <
         
          "<
          
           <

练习。16求某年某月某日是当年的第几天

/ ConsoleAppRunNian.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "iostream"#include "windows.h"using namespace std;int leap(int a)                                     /*自己定义函数leap用来指定年份是否为闰年*/  {  	if (a % 4 == 0 && a % 100 != 0 || a % 400 == 0)             /*闰年判定条件*/  		return 1;                                   /*是闰年返回1*/  	else  		return 0;                                   /*不是闰年返回0*/  }  int number(int year, int m, int d) /*自己定义函数number计算输入日期为该年第几天*/  {  	if ( m>12 || d > 31 || d < 0 || m<0)	{		cerr<<"參数错误!"<
      
        29)		{			cerr<<"參数错误!"<
       
        >year>>month>>day;             /*输入年月日*/  	n = number(year, month, day);                           /*调用函数number*/  		while (n == -1)	{		cout<<"请又一次输入年月日"<
        
         >year>>month>>day;             /*输入年月日*/  		n = number(year, month, day);                           /*调用函数number*/ 	}		cout<<"第"<
         
          <<"天"<

练习17，逻辑推理题

婚礼上的谎言

// ConsoleAppHunLi.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "iostream"#include "windows.h"using namespace std;int _tmain(int argc, _TCHAR* argv[]){	int a, b, c;	for (a = 1; a <= 3; a++)								/*穷举a的全部可能*/		for (b = 1; b <= 3; b++)							/*穷举b的全部可能*/			for (c = 1; c <= 3; c++)						/*穷举c的全部可能*/				if (a != 1 && c != 1 && c != 3 && a != b && a != c && b != c)					/*假设表达式为真，则输出结果。否则继续下次循环*/				{					cout<
      
       <<" 将嫁给 A"<

练习18，二维数组转换为一维数组：

// ConsoleAppMatTrans.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "iostream"using namespace std;/******************定义二维数组char array[x][y]; 1.仅仅定义个一维的就能够了 char *array; array = new char[x*y]; 这样的方式等价于char *array = new char[x*y];訪问的时候*(array+i*y+j)表示array[i][j] 2.定义一个二维数组 char **array1 array1 = new char *[x]; for(i=0;i
      
       >row>>col;	mat =new int*[row];//二维数组的每行的指针	cout<<"请输入二维数组："<
       
        >mat[i][j];		}	}		cout<<"二维数组为："<
        
         < row*col;k++)	{		cout<
         
          <<" ";	}	delete[] arr;	system("pause");	return 0;}int Trans2DArray(int **src2dArr,int nRow,int nCol,int *dst1dArr){	if (src2dArr == NULL || nRow < 0 || nCol <0)	{		cerr<<"參数错误"<

练习19,求取一个二进制数的长度

定义：二进制长度就是最高位1的下标值+1（下标从0開始），比方16 = 10000。则长度是5， 2= 0010。长度为2

#include "stdafx.h"#include "iostream"using namespace std;int BitLength(unsigned int n);int _tmain(int argc, _TCHAR* argv[]){	int count=0,a;	do 	{	cout<<"请输入一个整数"<
      
       >a;	count=BitLength(a);	cout<<"该整数相应二进制数的长度为："<
       
        <
        
         0);	return 0;}//算法一：易阅读int BitLength(unsigned int n){	int c = 0 ;  //计数	while (n)	{		++c ;		n >>= 1 ;	}	return c ;}//算法二：与上面的解法本质一样int BitLength(unsigned int n) {     return n ? BitLength1(n >>=1) + 1 : 0 ; }//算法三：以空间换时间（參考网络）int BitLength(unsigned int n) {     // pow of 2, 2^0 - 2 ^31     int powof2[32] =     {                  1,           2,           4,           8,         16,          32,                 64,         128,         256,         512,       1024,        2048,               4096,        8192,       16384,       32768,      65536,      131072,             262144,      524288,     1048576,     2097152,    4194304,     8388608,           16777216,    33554432,    67108864,   134217728,  268435456,   536870912,         1073741824,  2147483648     } ;     int left = 0 ;     int right = 31 ;     while (left <= right)     {         int mid = (left + right) / 2 ;         if (powof2[mid] <= n)         {             if (powof2[mid + 1] > n)                 return mid + 1; // got it!             else // powof2[mid] < n, search right part                left = mid + 1 ;         }         else // powof2[mid] > n, search left part             right = mid - 1 ;     }      return -1 ; }

练习20，求两个正整数的最大公约数

碾转相除法：如果f（a，b）是a，b的最大公约数，则f（b。a%b）=f（a。b）。即f（b，a%b）相同也是其最大公约数

#include "stdafx.h"#include
      
       using namespace std;int GyueNum(int x,int y);int main(){	int a,b,result;	cout<<"请输入两个随意的整数"<
       
        >a>>b;	result=GyueNum(a,b);	cout<
        
         <

练习21,栈的顺序输出（STL库实现）

// ConsoleAppStackTest1.cpp : 定义控制台应用程序的入口点。///**函数功能：以 23 56 11 4 87 98入栈，以11 4 56 98 87 23出栈*函数原形：无*參数：无*返回值：无*时间复杂度：无*备注：无*日期：2014/12/13*原创：是*作者：EbowTang*Email：tangyibiao520@163.com*/#include "stdafx.h"#include 
      
       #include 
       
        using namespace std;int _tmain(int argc, _TCHAR* argv[]){	//顺序入栈，三个參数	stack
        
          sta;		sta.push( 23 );	sta.push( 56 );	sta.push( 11 );	cout << sta.top( )<< " ";//输出顶值11	sta.pop( );//删除元素11		sta.push( 4 );	cout << sta.top( )<< " ";//输出顶值4	sta.pop( );//删除元素4	cout << sta.top( ) << " ";//输出顶值56	sta.pop( );//删除元素56	sta.push( 87 );	sta.push( 98 );	cout << sta.top( ) << " ";//输出顶值98	sta.pop( );//删除元素98	cout << sta.top( ) << " ";//输出顶值87	sta.pop( );//删除元素87	cout << sta.top( ) << " ";//输出顶值23	system( "PAUSE" );	return EXIT_SUCCESS;}

练习22，括号配对问题

描写叙述

如今。有一行括号序列。请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组測试数据。

后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），測试数据组数少于5组。数据保证S中仅仅含有"[","]","(",")"四种字符

输出

每组输入数据的输出占一行，假设该字符串中所含的括号是配对的，则输出Yes,假设不配对则输出No

例子输入

3[(])(])([[]()])

例子输出

NoNoYes

难度3，第2题

方法：（栈的基本运用）

解题思路依次扫描整个字符串，并使用栈进行模拟。对于输入括号（假设不特殊指出，这里的
括号均指的是含圆括号和中括号）
1，假设为左型的括号（比方 “[” “(”）则入栈
2。假设为右型括号且栈为空或栈顶元素与之不配对则输出No，反之弹出栈顶元素
3，反复1和2步骤直到扫描结束，最后检查栈是否为空，若为空输出Yes反之输出No。

“括号配对”代码实现例如以下：

#include "iostream"  #include "string"  #include "stack"  using namespace std;bool BracketMatch(const string srcStr);int _tmain(int argc, _TCHAR* argv[]){	system("color 0A");	int N = 0;	//申请内存  	string src;	while (cin>>N)	{		for (size_t i = 0; i < N; i++)		{			cin >> src;			if (BracketMatch(src))				cout << "YES" << endl;			else				cout << "NO" << endl;		}	}	return 0;}bool BracketMatch(const string srcStr){	stack
       
         s;	//样例[]()[];  	if (srcStr[0] == ')' || srcStr[0] == ']')//假设第一个字符就是右括号，则直接pass掉  		return false;			for (unsigned int i = 0; i < srcStr.length(); i++)//从左往右開始遍历  	{		switch (srcStr[i])		{			//对左括号仅作压栈处理，同一时候值得注意的是栈中仅仅有左括号			case '[':					s.push(srcStr[i]);					break;			case '(':					s.push(srcStr[i]);					break;			//对于右括号总是推断他是否与栈顶元素配对，否则就可以推断不配对  			case ']':					if (s.top() == '[')						s.pop();					break;			case ')':					if (s.top() == '(')						s.pop();					break;			default:					cerr << "错误的括号" << endl;					exit(1);		}			}	//推断栈中的情况	if (s.empty())		return true;	else//假设栈中有数据则说明存在不匹配		return false;}

练习23。奇偶数分离

描写叙述

有一个整型偶数n(2<= n <=10000),你要做的是：先把1到n中的全部奇数从小到大输出，再把全部的偶数从小到大输出。

输入

第一行有一个整数i（2<=i<30)表示有 i 组測试数据；

每组有一个整型偶数n。

输出

第一行输出全部的奇数

第二行输出全部的偶数

例子输入

例子输出

1 3 5 7 9 2 4 6 8 10 1 3 5 7 9 11 13 2 4 6 8 10 12 14

难度1。第11题

方法：

直接破题。即直接依据题意输出指定内容

“奇偶数分离”代码实现例如以下:

// ConsoleAppAcmTest11.cpp : 定义控制台应用程序的入口点。

// #include "stdafx.h" #include "iostream" using namespace std; void OddEvenSepar(int *num, int N) { for (int i = 0; i < N;i++) { int k = 1; while (k < num[i]) { if (k % 2 == 1) { cout << k << " "; } k++; } cout << endl; int kk = 1; while (kk < num[i]) { if (kk % 2 == 0) { cout << kk << " "; } kk++; } cout << endl; } } int _tmain(int argc, _TCHAR* argv[]) { system("color 0A"); int N = 0; cout << "请输入測试组数：" << endl; cin >> N; int *num = new int[N]; cout << "请输入相应个数的偶数" << endl; for (int i = 0; i < N;i++) { cin>>num[i]; } cout << endl; OddEvenSepar(num, N); delete[] num; num = NULL; system("pause"); return 0; }

练习24。五个数求最值

描写叙述

设计一个从5个整数中取最小数和最大数的程序

输入

输入仅仅有一组測试数据，为五个不大于1万的正整数

输出

输出两个数。第一个为这五个数中的最小值，第二个为这五个数中的最大值。两个数字以空格格开。

例子输入

1 2 3 4 5

例子输出

1 5

难度：1。第31题

方法：

排序法。或者直接求取

“五个数求最值”代码实现例如以下：

// ConsoleAppAcmTest31.cpp : 定义控制台应用程序的入口点。

// #include "stdafx.h" #include "iostream" using namespace std; void getMinMax(int *num,int n) { int min = num[0], max = num[0]; for (int j = 0; j < n;j++) { if (min>num[j]) { min = num[j]; } if (max < num[j]) { max = num[j]; } } cout << "最小值为：" << min << endl; cout << "最大值为：" << max << endl; } int _tmain(int argc, _TCHAR* argv[]) { system("color 0A"); int num[5] = {0}; for (int i = 0; i < 5;i++) { cin >> num[i]; } getMinMax(num,5); system("pause"); return 0; }

练习25，韩信点兵

描写叙述

相传韩信才智过人。从不直接清点自己军队的人数，仅仅要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次仅仅掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7）。输出总人数的最小值（或报告无解）。已知总人数不小于10。不超过100 。

输入

输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7）。

比如,输入：2 4 5

输出

输出总人数的最小值（或报告无解。即输出No answer）。实例。输出：89

例子输入

2 1 6

例子输出

难度1,第34题

方法：

暴力破解。遍历出答案

// ConsoleAppAcmTest34.cpp : 定义控制台应用程序的入口点。

// #include "stdafx.h" #include "iostream" using namespace std; int HanXinCount(int *num); int _tmain(int argc, _TCHAR* argv[]) { system("color 0A"); int *num = new int[3]; cout << "请输入3种排列方式的队尾人数："<<endl; for (int i = 0; i < 3;i++) { cin >> num[i]; } int persons = HanXinCount(num); if (persons==-1) { cout << "No Answer" << endl; } else { cout << "人数共为:" << persons << endl; } delete[] num; num = NULL; system("pause"); return 0; } int HanXinCount(int *num) { int persons = -1; for (int i = 10; i <= 100;i++) { if ( i%3==num[0] && i%5==num[1] && i%7==num[2]) { persons = i; } } return persons; }

练习26，组合数

描写叙述

找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)个数的全部组合。

输入

输入n、r。

输出

按特定顺序输出全部组合。

特定顺序：每个组合中的值从大到小排列。组合之间按逆字典序排列。

例子输入

5 3

例子输出

543542541532531521432431421321

难度3。第32题

方法：

DFS法，深度遍历型程序设计

“组合数”代码实现例如以下：

// ConsoleAppAcmTest32.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "iostream"using namespace std;int a[11];bool visit[11];//存放数据被訪问否void DFSCombiNum1(int n,int cur, int r);void printNum(int *w, int r);int _tmain(int argc, _TCHAR* argv[]){	system("color 0A");	int n = 5;	int r = 3;	cout << "确定范围1到n：请输入n的详细值"<
      
       > n;	while (n>10)	{		cout << "又一次确定范围1到n：请输入n的详细值" << endl;		cin >> n;	}	cout << "从1到n取r个数：请输入r的详细值" << endl;	cin >> r;	while (r > n)	{		cout << "又一次输入r" << endl;		cin >> r;	}	memset(visit, false, sizeof(visit));//初始化	DFSCombiNum1(n,1, r);	system("pause");	return 0;}//递归法DFSvoid DFSCombiNum1(int n, int cur, int r) //入口、当前层、总层数  {	if (cur > r) //结束条件  		return;	for (int i = n; i >= 1; i--)//从n遍历到1，	{		if (!visit[i])//当前这个数没有被訪问过，则訪问他		{			visit[i] = true;			a[cur] = i;//记录要输出的数字			if (cur == r)//每次当cur添加到r时就输出放在a中的数			{				printNum(a, r);			}			DFSCombiNum1(i - 1, cur + 1, r);			visit[i] = false;		}	}}void printNum(int *a, int r){	for (int i = 1; i <= r; i++)	{		cout << a[i];	}	cout << endl;}

练习27，计算超大数相乘：

编写两个超大数相乘,不用考虑负数

#include 
      
       #include 
       
        using namespace std;void Multiply(const string &a, const string &b, vector
        
          &ansStr);int main(){	string bigNum1, bigNum2;     // 初始状态用string来存储大数	while (cin >> bigNum1 >> bigNum2)	{		vector
         
           ans(bigNum1.size() + bigNum2.size(), 0);//接收答案，这里必须给予ans大小。否则传递參数时out of range		Multiply(bigNum1, bigNum2, ans);		for (unsigned int i = 1; i < ans.size(); i++)				cout << ans[i];		cout << endl;		ans.clear();	}	return 0;}void Multiply(const string &a, const string &b, vector
          
            &ans){	int lena = a.length(),lenb = b.length();	for (int i = 0; i < lena; i++)	{		for (int j = 0; j < lenb; j++)		{//25,a[0]=2,a[1]=5，31，b[0]=3,b[1]=1;推出==》ans[1]=6,ans[2]=17,ans[3]=5，（ans[0]=0）			ans[i + j + 1] += (a[i] - '0')*(b[j] - '0');		}}		for (int i = lena + lenb - 1; i >= 0; i--)// 这里实现进位操作	{		if (ans[i] >= 10)		{			ans[i - 1] += ans[i] / 10;//让高位获得来自低位的进位值，注意ans[i]相对ans[i-1]是低位			ans[i] %= 10;//低位自裁,仅仅保留当前数的个位就可以,比方223，仅仅保留3,22给高位		}}}

练习28。单词的部分逆置

举例。“I am Chinese.”

逆置后为”Chinese. am I“

參考代码：

#include "string"#include "vector"#include 
      
       using namespace std;int main(){	string str;	while (getline(cin,str))	{		//以此为例 "I am Chinese."		int i = 0, j = str.size() - 1;		char temp;		//逆置字符串。"esenihC. ma I"		while (j > i)		{			temp = str[i];			str[i] = str[j];			str[j] = temp;			i++; j--;		}		//部分反转,"Chinese. am I"		int begin = 0, end = 0;		int ii = 0;		while (ii < str.size())		{			if (str[ii] != ' ')//寻找空格前的子串			{				begin = ii; 				while (str[ii] != ' '&& ii < str.size())//这里考虑了在计数最后一个字符时的情况				{					ii++;				}				ii--;				end = ii;			}			while (end > begin)			{				temp = str[begin];				str[begin++] = str[end];				str[end--] = temp;			}			ii++;		}		cout << str << endl;	}	return 0;}

练习29。

PS:有的东西表面看上去公正、全面，实际可能走向极端的分立思维，很多客观事物不能简单均分，可能其内在具有复杂的联系。一旦坚持平分，结果倒失去了客观、全面的基础。

折半搜索每次把搜索区域降低一半。时间复杂度为

O\left( \log n \right)

。（n代表集合中元素的个数）

O\left( 1 \right)

。虽以递归形式定义，可是。可改写为循环

维基百科告诉我们要这样写：为什么呢？

[cpp]
 <span style="font-size:12px;">//递归版本号  
 int binary_search( const int arr[], int low, int high, int key)  
 {  
    int mid = low+(high-low)/2; // 别用 (low+high)/2 ，由于可能引起溢出问题。  
    if(low>high)  
        return -1;  
    else  
      {  
        if(arr[mid]==key)  
           return mid;  
        else if(arr[mid]>key)  
           return binary_search(arr,low,mid-1,key);  
        else   
           return binary_search(arr,mid+1,high,key);  
      }  
 }</span>  

開始分析

一般二分法这样写：

[cpp]
 <span style="font-size:12px;">int binarySearch(int arr[], int l, int h, int key)  
 {  
     while (l <= h)  
     {  
         // find index of middle element  
         int m = (l+h)/2;  
    
         // Check if key is present at mid  
         if (arr[m] == key) return m;  
    
         // If key greater, ignore left half  
         if (arr[m] < key) l = m + 1;  
    
         // If key is smaller, ignore right half  
         else h = m - 1;  
     }  
    
     // if we reach here, then element was not present  
     return -1;  
 }</span>  

以上看起来没事，除了一个非常微妙的东西，表达“m =（l+r）/ 2″。

它不能用于l和r特别大的时候，假设l和r的总和大于最大正int值（2的31次方–1）。

将

溢出为负值，即求和之后成了负值时，再除以2也是负值。

这将

导致

索引超出

范围

和

不可预知的结果

。

所以解决问题的方法就是：

mid = ((unsigned int)low + (unsigned int)high)) >> 1 ;

或者

mid = low+(high-low)/2;

练习30，

构造函数是一个非常特殊的成员函数。当一个对象被创建时他将会自己主动被调用。

析构器也是一个非常特殊的成员函数，当对象在作用域结束时会被自己主动的隐式调用。当动态分配内存和销毁时也会调用这两个特殊的函数，即new和delete操作符！

进入正题，显式调用这两个特殊的函数：

[cpp]
 #include <iostream>  
 using namespace std;  
    
 class Test  
 {  
 public:  
     Test()  { cout << "Constructor is executed\n"; }  
     ~Test() { cout << "Destructor is executed\n";  }  
 };  
    
 int main()  
 {  
     Test();  // 显式调用构造器  
     Test t; // 创建本地对象  
     t.~Test(); // 显式调用析构器  
     return 0;  
 }  
 ///输出:  
   
 Constructor is executed   （Test（）显式调用产生的，同一时候会产生一个暂时对象。并立马销毁）  
 Destructor is executed    （暂时对象造成的，此时析构器被调用）  
 Constructor is executed   （创建本地对象产生的）  
 Destructor is executed    （显式调用析构器产生的。可是并不意味着对象被销毁）  
 Destructor is executed    （main结束时，析构函数在对象t作用域的末尾调用。起到释放资源的作用）  

当构造器被显式调用时，编译器立马创建了一个未命名的暂时对象。同一时候它也被立马销毁。这也是为什么输出中的第二行会是“析构器被运行”特别注意。假设对象时动态分配的内存。千万别显式调用析构器。由于delete会调用析构器。

类的成员函数也能调用析构器和构造器

[cpp]
 #include <iostream>  
 using namespace std;  
    
 class Test  
 {  
 public:  
     Test()  { cout << "Constructor is executed\n"; }  
     ~Test() { cout << "Destructor is executed\n";  }  
     void show()  {  Test();  this->Test::~Test();  }  
 };  
    
 int main()  
 {  
     Test t;  
     t.show();  
     return 0;  
 }  
 输出:  
   
 Constructor is executed  
 Constructor is executed  
 Destructor is executed  
 Destructor is executed  
 Destructor is executed  

最后再来分析一段程序：

[cpp]
 #include <iostream>  
 using namespace std;  
    
 class Test  
 {  
 public:  
     Test()  { cout << "+++"; }  
     ~Test() { cout << "---";  }  
     friend void fun(Test t);  
 };  
 void fun(Test t)  
 {  
     Test();//析构器和构造器均会被调用  
    t.~Test();//显式调用析构器............然后就完了吗？对象t在这个函数的末尾被自己主动在调用一次析构器！！。
  
 }  
 int main()  
 {  
     Test();//输出+++，然后---  
     Test t;//输出+++  
     fun(t);//输出+++。---，---，---  
     return 0;//输出---  
 }  

所以输出为：

[cpp]
 +++  
 ---  
 +++  
 +++  
 ---  
 ---  
 ---  
 ---  

有时候显示调用析构器是实用的，微软告诉我们：

非常少须要显式调用析构函数。

可是。对置于绝对地址的对象进行清理会非常实用。这些对象通常使用採用位置參数的用户定义的 new 运算符进行分配。 delete 运算符不能释放该内存，由于它不是从自由存储区分配的（有关具体信息，请參阅）。可是。对析构函数的调用能够运行对应的清理。

若要显式调用 String 类的对象 s 的析构函数，请使用下列语句之中的一个：

s.String::~String();     // Nonvirtual callps->String::~String();   // Nonvirtual calls.~String();       // Virtual callps->~String();     // Virtual call

能够使用对前面显示的析构函数的显式调用的表示法，不管类型是否定义了析构函数。这同意您进行此类显式调用，而无需了解是否为此类型定义了析构函数。

显式调用析构函数。当中没有定义的析构函数无效。

练习31，调整数组结构

模拟小波变换中LL,HL,LH,HH系数调整

#include "iostream" #include "windows.h"#include "fstream"#include "algorithm" using namespace wavelet;using namespace std;bool AdjustData(	double *pDetCoef,	const int height,	const int width	){	if (pDetCoef == NULL)		return false;	double *ptmpdet = new double[height / 2 * width];	for (int i = 0; i < height / 2 * width; i++)		ptmpdet[i] = pDetCoef[i];	int pos1 = 0;	int pos2 = height / 2 * width / 2;	for (int i = 0; i < height / 2; i++)	{		for (int j = 0; j < width; j++)		{			if (j < width / 2)				pDetCoef[pos1++] = ptmpdet[i*width + j];			else				pDetCoef[pos2++] = ptmpdet[i*width + j];		}	}	delete[] ptmpdet;	ptmpdet = NULL;	return true;}bool IAdjustData(	double *pDetCoef,	const int height,	const int width	){	if (pDetCoef == NULL)		return false;	double *ptmpdet = new double[height / 2 * width];	for (int i = 0; i < height / 2 * width; i++)		ptmpdet[i] = pDetCoef[i];	int pos1 = 0;	int pos2 = height / 2 * width / 2;	for (int i = 0; i < height / 2; i++)	{		for (int j = 0; j < width; j++)		{			if (j < width / 2)				pDetCoef[i*width + j] = ptmpdet[pos1++];			else				pDetCoef[i*width + j] = ptmpdet[pos2++];		}	}			delete[] ptmpdet;	ptmpdet = NULL;	return true;}int main(){	system("color 0A");	double s[30] = {1,2,3,4,5,6,  2,3,4,5,6,7,  3,4,5,6,7,8,  4,5,6,7,8,9, 5,6,7,8,9,10};	int height = 5;	int width = 6;	for (int i = 0; i < height; i++)	{		for (int j = 0; j < width; j++)			cout << s[i*width + j] << " ";		cout << endl;	}	cout << endl; cout << endl;	AdjustData(s,height,width);	for (int i = 0; i < height; i++)	{		for (int j = 0; j < width; j++)			cout << s[i*width + j] << " ";		cout << endl;	}	IAdjustData(s, height, width);	cout << endl; cout << endl;	for (int i = 0; i < height; i++)	{		for (int j = 0; j < width; j++)			cout << s[i*width + j] << " ";		cout << endl;	}	system("pause");	return 0;}