Yu han の BLog

/**
*auther:@却水
*edit time:2019-03-07
*@xi'an University of science & technology
*@Software engineering 1703 17408070828

*/



#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <Windows.h>
#define N 5000

using namespace std;
//辗转相除法嵌套调用
int divisor(int a,int b)//最大公约数

{
	
	int temp;
	if(a>b)
	{
		temp=a;a=b;b=temp;
	}
	while(b!=0)
	{
		temp=a%b;
		a=b;
		b=temp;
	}
   
	return (a);  
}
int multiple(int a,int b)//最小公倍数
{
	int divisor(int a,int b);
		int temp;
	temp=divisor(a,b);
	return(a*b/temp);
}

int gcd (int a,int b)//递归调用
   
	{
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}


//穷举法
int divisor1(int a,int b)
{ 
	int temp;
	temp=(a>b)?b:a;
	while(temp>0)
	{if(b%temp==0&&a%temp==0)
		break;
	temp--;
	} 
	
return(temp);
}
int multiple1(int a,int b)
{
	int p,q,temp;
	p=(a>b)?a:b;//较大值
	q=(a>b)?b:a;//较小值
	temp=p;
	while(1)
	{
		if(p%q==0)
			break;
		p+=temp;
	}
	
return p;
}
//更相减损术
int gcd1(int a,int b)
{
	int i=0,temp,x;
	while(a%2==0&&b%2==0)//两数都是偶数
	{a/=2;
	b/=2;
	i++;//计算共有几个2
	}
	if(a<b)
	{
		temp=a;
		a=b;
		b=temp;
	}
	while(x)
	{
		x=a-b;
		a=(b>x)?b:x;
		b=(b<x)?b:x;
		if(b==(a-b))
			break;
	}
	if(i=0)
		return b;
	else
		return (int)pow(2,i)*b;//计算更相减损后的乘积

}
//stein
int Stein(unsigned int x,unsigned int y)//返回a,b中的最大公约数

/* return the greatest common divisor of x and y */
{
  int factor = 0;
  int temp;

  if ( x < y )
{
     temp = x;
     x = y;
     y = temp;                      
 }                  
  if ( 0 == y )    
    {
    return 0;            
   }         
   while ( x != y )     
   {     
    if ( x & 0x1 )            
  {//x为偶数              
     if ( y & 0x1 )                   
    {/* when x and y are both odd */                    
        y = ( x - y ) >> 1;                        
          x -= y;                      
   }                     
    else                    
 {/* X为偶数y为奇数 */                       
y >>= 1;                                
       }                 
    }            
    else             
  {/* x为奇数 */              
    if ( y & 0x1 )                    
  {/* x为奇数y为偶数 */                      
   x >>= 1;                             
   if ( x < y )                             
   {                             
     temp = x;                                   
      x = y;                                  
       y = temp;                                 
     }                           
      }                  
   else                     
{/* when x and y are both even */                        
 x >>= 1;                               
  y >>= 1;                              
  ++factor;                              
      }                  
    }            
}        
return ( x << factor );        

}


int gcd_run(int u,int v)//stein递归
{
    if (u == 0) return v;
    if (v == 0) return u;
    // look for factors of 2
    if (~u & 1) // u is even
    {
        if (v & 1) // v is odd
            return gcd(u >> 1, v);
        else // both u and v are even
            return gcd(u >> 1, v >> 1) << 1;
    }
     if (~v & 1) // u is odd, v is even
        return gcd(u, v >> 1);
     // reduce larger argument
    if (u > v)
        return gcd((u - v) >> 1, v);
     return gcd((v - u) >> 1, u);
}
void main()
{
int i,a;
cout<<"请输入测试数据组数"<<endl;
/*
数据异常处理

*/
    int ret;
    ret = scanf("%d",&a);
    while (ret != 1)
    {
        while (getchar() != '\n');
		printf("error input,please again.\n");
        ret = scanf("%d",&a);
    }//直到输入的值为整数
	 
int arr[N] ;
srand((unsigned)time(NULL));//调用time函数来获取随机数
for (i = 0; i< N; i++)
{
arr[i] = rand(); //随机数组


}cout<<"                       检验数据是否随机"<<endl;
for(i=0;i<10;i++)
{
cout<<"                        ********"<<arr[i]<<"********"<<endl;
}
//计时函数
    double time=0;
    double counts=0;
    LARGE_INTEGER nFreq;
	LARGE_INTEGER nBeginTime;
	LARGE_INTEGER nEndTime;
	QueryPerformanceFrequency(&nFreq);

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++){
divisor(arr[i],arr[i+2]);//调用辗转相除法函数
}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"辗转相除法(非递归)时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
gcd(arr[i],arr[i+2]);//辗转相除递归调用

}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"辗转相除法(递归)时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
divisor1(arr[i],arr[i+2]);//穷举法函数调用QueryPerformanceCounter(&nEndTime);//停止计时

}time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"穷举法时间为："<<(-time*1000)<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
	gcd1(arr[i],arr[i+2]);//更相减损术算法

}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"更相减损术算法时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{
Stein(arr[i],arr[i+2]);//Stein
}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"Stein算法时间为："<<time*1000<<"ms"<<endl;

QueryPerformanceCounter(&nBeginTime);
for(i=0;i<2*a;i++)
{i+=1;gcd_run(arr[i],arr[i+2]);//Stein递归调用
}
QueryPerformanceCounter(&nEndTime);//停止计时
time=(double)(nEndTime.QuadPart-nBeginTime.QuadPart)/(double)nFreq.QuadPart;//计算程序执行时间单位为s
cout<<"Stein（递归）时间为："<<time*1000<<"ms"<<endl;
}

int Date_fish::Deal_key()
{
    cout<<"请输入年"<<endl;
    cin>>year;
      //判断输入的年，月，日是否在规定的范围
   if (year<2010||year>2019) //判断年
    {
        cout<<"年份输入错误，请输入2010-2019范围的年份（包含2010和2019)"<<endl;
        
		cin>>year;
    } 
    cout<<"请输入月"<<endl;
    cin >>month;
     if(month<=0||month>12) //判断月
    {
        cout<<"月份输入错误，请输入1-12范围的月份（包含1和12)"<<endl;
        cin>>month;
    }
    
	 
	 cout<<"请输入日"<<endl;
    cin>>day;

 if(month==1||month==3||month==5||month==7||month==8||month==10||month==12)//判断日  
 {
	 if(day>31||day<=0)//判断大月
	 {cout<<"天数输入错误，请输入改后的正常天数"<<endl;
	 cin>>day;
	 }
 }
 else if(month!=2)//判断小月
	 if(day>30||day<=0)
	 {{cout<<"您输入的日期有误，请重新输入"<<endl;
	 cin>>day;}
 }
 else if(((year%4==0&&year%100!=0)||year%400==0))//判断闰年2月
 {
	 if(day>29||day<=0)
	 {cout<<"您输入的日期有误，请重新输入"<<endl;
	  cin>>day;
	 }

 }
 else
 {
	 if(day>28||day<=0)
	 {cout<<"您输入的日期有误，请重新输入"<<endl;
	 cin>>day;}
	 return 0;
 }
}

void Date_fish::sumdays() //判断平闰年函数并计算天数
{
    int YEAR_0=2010; //定义初始变量YEAR_0为2010
    for (YEAR_0;YEAR_0<year;YEAR_0++) //距当前年份几年，循环几次
    {
        if((year%400==0)||(year%4==0&&year%100!=0)) //当前年份为闰年，||前为世纪年判断，||后为普通年
        {
            sum+=366;//闰年，总天数加366天
        }
        else//为平年
        {
            sum+=365; //平年，总天数加365天
        }
    }
    for(int i=0;i<month-1;i++)
    {
		if((year%400==0)||(year%4==0&&year%100!=0))
        sum+=special_month_day[i]; //加当前月份的天数
        else
		sum+=normal_month_day[i];
    }
    sum+=day; //总天数
	cout<<"到2010-01-01的总天数为：";
	cout<<sum<<endl;

    days_5=sum%5;//除5取余
    sum=0;//初始化
   //return days_5;
}

void Date_fish::display()
 {
	  
	if (days_5>=1&&days_5<4)//余数1,2,3
    {
        //余数1,2,3打鱼
        cout<<"这天在打鱼"<<endl;
    } 
    else
    {
        //晒网
        cout<<"这天在晒网"<<endl;
    }
   //return days_5;
 }

int Date_fish::file()

{int a[3];//数组实现txt文档中三个值的传回 
ifstream infile("in.txt",ios::in);
if(!infile)
{cerr<<"open in.txt error!"<<endl;
exit(1);
}
infile>>a[0]>>a[1]>>a[2];
year=a[0]; month=a[1]; day=a[2];

sumdays();//接收计算后的days_5
//
ofstream outfile("out.txt",ios::out);

{if (days_5>0&&days_5<4)
   {
        outfile<<year<<"."<<month<<"."<<day<<"该天打鱼"<<endl; //余数为1或2或3，将打鱼的信息写入out文件中
   } 
   else
   {
        outfile<<year<<"."<<month<<"."<<day<<"该天晒网"<<endl;//余数为0或4，将晒网的信息写入out文件中

   }
}
   //关闭文件
   infile.close(); 
   outfile.close();
    return 0;
}

/*~
#@**xi'an university of science & technology**
#@Software engineering 1703 
#@17408070828
~*/

#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;
class Date_fish{
public :
    int year; //年
    int month; //月
    int day; //日
    Date_fish();//构造函数
    int file(); //对文件中的信息进行处理
    int Deal_key();//对从键盘输入的信息进行处理
    int Choose;////键盘读入或文件读入的选择标志
    void sumdays();//判断闰年平年
	void display();//工作类型
    int days_5; //除5的余数
    int sum; //距2010年1月1日的总天数
    int normal_month_day[12]; //平年每月的天数
	int special_month_day[12];
};
Date_fish::Date_fish () //构造函数初始化
{
     Choose=0; //键盘读入或文件读入的选择标志
     sum=0;
     days_5=0; 
     year=0;
     month=0;
     day=0;
     int normal_month_day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
	 int special_month_day[12]={31,29,31,30,31,30,31,31,30,31,30,31};//初始平闰年各月份天数

}
int Date_fish::Deal_key()
{
    cout<<"请输入年"<<endl;
    cin>>year;
      //判断输入的年，月，日是否在规定的范围
   if (year<2010||year>2019) //判断年
    {
        cout<<"年份输入错误，请输入2010-2019范围的年份（包含2010和2019)"<<endl;
        
		cin>>year;
    } 
    cout<<"请输入月"<<endl;
    cin >>month;
     if(month<=0||month>12) //判断月
    {
        cout<<"月份输入错误，请输入1-12范围的月份（包含1和12)"<<endl;
        cin>>month;
    }
    
	 
	 cout<<"请输入日"<<endl;
    cin>>day;

 if(month==1||month==3||month==5||month==7||month==8||month==10||month==12)//判断日
    
 {
	 if(day>31||day<=0)//判断大月
	 {cout<<"天数输入错误，请输入改后的正常天数"<<endl;
	 cin>>day;
	 }

 }
 else if(month!=2)//判断小月
	 if(day>30||day<=0)
	 {{cout<<"您输入的日期有误，请重新输入"<<endl;
	 cin>>day;}
	
   
 }
 else if(((year%4==0&&year%100!=0)||year%400==0))//判断闰年2月
 {
	 if(day>29||day<=0)
	 {cout<<"您输入的日期有误，请重新输入"<<endl;
	  cin>>day;
	 }

 }
 else
 {
	 if(day>28||day<=0)
	 {cout<<"您输入的日期有误，请重新输入"<<endl;
	 cin>>day;}
	 return 0;
 }
}
void Date_fish::sumdays() //判断平闰年函数并计算天数
{
    int YEAR_0=2010; //定义初始变量YEAR_0为2010
    for (YEAR_0;YEAR_0<year;YEAR_0++) //距当前年份几年，循环几次
    {
        if((year%400==0)||(year%4==0&&year%100!=0)) //当前年份为闰年，||前为世纪年判断，||后为普通年
        {
            sum+=366;//闰年，总天数加366天
        }
        else//为平年
        {
            sum+=365; //平年，总天数加365天
        }
    }
    for(int i=0;i<month-1;i++)
    {
		if((year%400==0)||(year%4==0&&year%100!=0))
        sum+=special_month_day[i]; //加当前月份的天数
        else
		sum+=normal_month_day[i];
    }
    sum+=day; //总天数
	cout<<"到2010-01-01的总天数为：";
	cout<<sum<<endl;

    days_5=sum%5;//除5取余
    sum=0;//初始化
   //return days_5;
}

	 
void Date_fish::display()
 {
	  
	if (days_5>=1&&days_5<4)//余数1,2,3
    {
        //余数1,2,3打鱼
        cout<<"这天在打鱼"<<endl;
    } 
    else
    {
        //晒网
        cout<<"这天在晒网"<<endl;
    }
   //return days_5;
 }

int Date_fish::file()

{int a[3];//数组实现txt文档中三个值的传回 
ifstream infile("in.txt",ios::in);
if(!infile)
{cerr<<"open in.txt error!"<<endl;
exit(1);
}
infile>>a[0]>>a[1]>>a[2];
year=a[0]; month=a[1]; day=a[2];

sumdays();//接收计算后的days_5
//
ofstream outfile("out.txt",ios::out);

{if (days_5>0&&days_5<4)
   {
        outfile<<year<<"."<<month<<"."<<day<<"该天打鱼"<<endl; //余数为1或2或3，将打鱼的信息写入out文件中
   } 
   else
   {
        outfile<<year<<"."<<month<<"."<<day<<"该天晒网"<<endl;//余数为0或4，将晒网的信息写入out文件中

   }
}
   //关闭文件
   infile.close(); 
   outfile.close();
    return 0;
}
int main()
{
    Date_fish m;
   cout<<"请选择日期读取方式："<<endl;
   cout<<"*******0为从键盘读取*******"<<endl;
   cout<<"*******1为从文件读取*******"<<endl;
   cin>>m.Choose;
   
   //
   switch(m.Choose)
   {
   case 0:
       {m.Deal_key();
	   m.sumdays();
       m.display();}
	   break;
   case 1:
       m.file();
       break;
}
    return 0;
}
/*-----------
auther @却水*/