[筆記試験]常考アルゴリズム
59027 ワード
#include<iostream>
using namespace std;
#include<cmath>
#include<iomanip>
//
/*class ClassA
{
public:
ClassA()
{
cout<<"A "<<endl;
}
~ClassA()
{
cout<<"A "<<endl;
}
virtual void getnum()=0;
//{
// cout<<"A "<<endl;
//}
private:
int num;
char *str;
double dnum;
};
class ClassB:public ClassA
{
public:
ClassB()
{
cout<<"B "<<endl;
}
~ClassB()
{
cout<<"B "<<endl;
}
virtual void getnum()
{
cout<<"B "<<endl;
}
private:
char Bstr[10];
};
void main()
{
ClassA *pc;
ClassB B;
pc=&B;
pc->getnum();
getchar();
}*/
/*
class ClassA
{
public:
virtual void getnum()
{
cout<<"A "<<endl;
}
};
class ClassB:public ClassA
{
public:
virtual void getnum()
{
cout<<"B "<<endl;
}
};
void main()
{ ClassA *pc;
ClassB B;
pc=&B;
pc->getnum();
getchar();
}*/
/*
(a~z) 。 ， ，
。
“abacacde” “abcde”。
*/
void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr)
{
//const char *TempStr=pInputStr;
int count1=0;
int count2=0;
int i=0;
while(count1<=lInputLen)
{
for(i=0;i<=count2;)
{
if(*(pInputStr+count1)!=*(pOutputStr+i))//
i++;
else
break;
}
if(i>count2)
{
*(pOutputStr+count2)=*(pInputStr+count1);
count2++;
}
count1++;
}
}
/* (a~z) 。 ， ，
。
：
1. 。 "abcbc" ， "abcbc".
2. " + "。 ： "xxxyyyyyyz" "3x6yz"*/
void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr)
{
int i=0;
int j=0;
int k=0;
for(i=0;i<lInputLen;i=j)
{
for(j=i+1;j<lInputLen;j++)
if(*(pInputStr+j)!=*(pInputStr+i))
break;
if(j!=i+1)
*(pOutputStr+k++)=char(j-i+'0');
*(pOutputStr+k++)=*(pInputStr+i);
}
}
/*
（50 ）：
100 、 ， 。
：“ 1 2”，“ ” “ ” 。
：
1. ， 。
2. ， “0”。
：
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr);
【 】 pInputStr：
lInputLen：
【 】 pOutputStr： ， ， ；
【 】 ， IO
：“4 + 7” ：“11”
：“4 - 7” ：“-3”
：“9 ++ 7” ：“0” ：
*/
bool Isnumber(char c)
{
if(c<='9'&&c>='0'){
return true;
}else{
return false;
}
}
void arithmetic(const char *pInputStr, long lInputLen, char *pOutputStr)
{
int ops1=0;
int ops2=0;
int num=0;
char Coptr;
int i=0;
int j=0;
int isvailed=0;
while(Isnumber(pInputStr[i]))
{
ops1=ops1*10+(int)(pInputStr[i]-'0');
i++;
}
//cout<<ops1<<endl;
if(i==0)
isvailed=1;
while(pInputStr[i++]==' ');
//cout<<i<<endl;
j=i-1;
Coptr=pInputStr[j];//
//cout<<Coptr<<endl;
while(pInputStr[j++]==' ');
j=i+1;
while(Isnumber(pInputStr[j]))
{
ops2=ops2*10+(int)(pInputStr[j]-'0');
j++;
}
if(j==(i+1))
isvailed=1;
if(isvailed==1)
*pOutputStr='0';
else
{
switch(Coptr)
{
case '+':
num=ops1+ops2;
break;
case '-':
num=ops1-ops2;
break;
case '*':
num=ops1*ops2;
break;
case '/':
num=ops1/ops2;
break;
default:
*pOutputStr='0';
break;
}
}
if(num==0)
*pOutputStr='0';
int scale=100;
if(num<0)
{
*pOutputStr++='-';
num=-num;
}
for(int k=0;k<3;k++)
{
if(num/scale)
{
*pOutputStr++=char(num/scale+'0');
}
num=num%scale;
if(num==0)
{
*pOutputStr++=char('0');
break;
}
scale/=10;
}
}
/*1
：
（ ‘a’ ‘z’）， ， ：a->b,b->c,…,y->z,z->a；
， 2 。 ：aa bc，zz ab；
， 。
：
void convert(char *input,char* output)
【 】 char *input ,
【 】 char *output ，
【 】
：char*input="abcd"
：char*output="bcde"
：char*input="abbbcd"
：char*output="bcdcde" 3*/
void convert(char *input,char* output)
{
int i=0;
int j=0;
int k=0;
int temp=1;
while(input[j++]!='\0')
{
if(input[i-1]!=input[i])
output[k++]=input[i++]+1;
else
{
temp++;
if(temp==3)
output[k++]=input[i++]+1;
else
output[k++]=input[i++]+2;
}
}
}
/*2
：
（ “ ” ， ，
、 、 ； ）； ， ，
（ ， ）， ；
， ； ， 。
“ ” ， 。
：
void my_word(charinput[], char output[])
【 】 char input[],
【 】 char output[]，
【 】
：charinput[]="some local buses, some1234123drivers" ，
：charoutput[]="drivers local buses some"
：charinput[]="%A^123 t 3453i*()" ，
：charoutput[]=""*/
void my_word(char input[], char output[])
{
int i=0;
int j=0;
int len=0;
int k=0;
int s=0;
int m=0;
while(input[len++]!='\0');
cout<<len<<endl;
char *tstr=new char[len];
while(input[j]!='\0')
{
s=0;
for(i=j;i<len-1;)
{
if((input[i]>='a'&&input[i]<='z')||(input[i]>='A'&&input[i]<='Z'))
{
tstr[s++]=input[i++];
}
else
{
i++;
break;
}
}
if (s>1)
{
for(k=0;k<s;k++)
output[m++]=tstr[k];
output[m++]=' ';
}
j=i;
}
//cout<<j<<endl;
delete [] tstr;
}
/*【 】： iNumber
【 】： iNumber
【 】：0：
1：
*/
int isPrimNumber(int iNumber)
{
if(iNumber == 1)
return 0;
if(iNumber == 2)
return 1;
for(int i = 2; i <= sqrt((double)iNumber); ++ i)
{
if(iNumber % i == 0)
return 0;
}
return 1;
}
/*
【 】： iArray[]
【 】： iArray, nSize
【 】： cnt
*/
int func(int iArray[],int nSize)
{
int i=0;
int num=0;
double Array=0;
int cnt=0;
for(i=0;i<nSize;i++)
num+=iArray[i];
Array=num*1.0/nSize;
for(i=0;i<nSize;i++)
if(iArray[i]>=Array)
cnt++;
return cnt;
}
/*
【 】： ， 1221，232， 3;
【 】： iNumber
【 】：0: iNumber
1：iNumber
*/
int isPlalindromeNumber(int iNumber)
{
int src = iNumber;
int des = 0;
while(src)
{
des = des * 10 + src % 10;
src /= 10;
}
if(des != iNumber)
return 0;
return 1;
}
/*
【 】： iNumber , primNumber[]
【 】： iNumber
*/
void getPrim(int iNumber)
{
int primNumber[100]={2,3,5};
int trial=5;
int count=3;
do
{
int found=0;
trial+=2;
for(int i=0;i<count;i++)
{
found=(trial%(primNumber[i]))==0;
if(found)
break;
}
if(!found)
primNumber[count++]=trial;
}while(trial<iNumber);
int n=0;
for(int i=0;i<count;i++)
{
cout<<setw(10)<<*(primNumber+i);
n++;
if(n==5)
{
n=0;
cout<<endl;
}
}
}
int func(int x)
{
int countx =0;
while(x)
{
countx ++;
x = x&(x-1);
}
return countx;
}
/*********************************** **************************************************
O(n ) O(1)
：
， ， ， ，
， ， 。
， j ， ，
input[j + 1] = input[j];
input[j] = temp;
*/
void InsertionSort(int input[],int len)
{
int i,j,temp;
for (i = 1; i < len; i++)
{
temp = input[i]; /* ， */
for (j = i - 1;j>-1&&input[j] > temp ; j--) /* */
{
input[j + 1] = input[j]; /* */
input[j] = temp;
}
}
}
/* ， ，
， ，
。
O(n )， O(1)。
*/
void SelectSort(int input[],int len)
{
int i=0;// ,i
int j=0;// ，j
int temp=0;//
for(i=0;i<len;i++)
for(j=i+1;j<len;j++)
if(input[i]>input[j])
{
temp=input[j];
input[j]=input[i];
input[i]=temp;
}
}
/*
， 。
*/
void BubleSort(int input[],int len)
{
int i=0;//
int j=0;//
int temp=0;//
for(int i=0;i<len;i++)
{ for(int j=0;j<len-i-1;j++)
{
if(input[j]>input[j+1])
{
temp=input[j];
input[j]=input[j+1];
input[j+1]=temp;
}
}
}
}
/*
,n ， ， ，
O(nlogn), O(logn)
*/
int partition(int input[],int low,int high)
{
int pivotey=input[low];
low=low+1;
while(low<high)
{
while(low<high&&input[high>=pivotey])--high;
input[low]=input[high];
while(low<high&&input[low]<=pivotey)++low;
input[high]=input[low];
}
input[low]=pivotey;
return low;
}
void Qsort(int input[],int low,int high)
{
int pivoloc=0;
if(low<high)
{
pivoloc=partition(input,low,high);
Qsort(input,low,pivoloc-1);
Qsort(input,pivoloc+1,high);
}
}
//
int parseInt(char *str,int radix)
{
int i=0;
int j=0;
//
int len=strlen(str);
while(i<len)
if((*(str+i)>=48)&&(*(str+i)<=57)||(*(str+i)>=65)&&(*(str+i)<=90)||(*(str+i)>=97)&&(*(str+i)<=122))
i++;
else
break;
try
{
if(i<len||len==0)
throw " ";
}
catch(const char aMessage())
{
cout<<endl<<aMessage<<endl;
}
//
int temp=0;
int num=0;
j=len;
int k=0;
cout<<str<<endl;
while(j>=0)
{
if((*(str+k)>=65)&&(*(str+k)<=90))
temp=*(str+k)-54;
if((*(str+k)>=97)&&(*(str+k)<=122))
temp=*(str+k)-86;
if((*(str+k)>=48)&&(*(str+k)<=57))
temp=*(str+k)-48;
num+=(int)temp*pow((double)radix,(int)j-1);
j--;
k++;
}
try
{
if(!(num>=-32768||num<=32767))
throw " ";
}
catch(const char aMessage())
{
cout<<endl<<aMessage<<endl;
}
return num;
}
// ， 100 ， ， ，
int lag(int num)
{
int chken=0;
int rubb=0;
int k=0;
int snum=0;
while(chken<=(num/2))
{
k=(num-chken*2)%4;
rubb=(num-chken*2)/4;
if(k==0)
{
cout<<" "<<chken<<" "<<" "<<rubb<<endl;
snum++;
}
chken++;
}
cout<<" "<<snum<<endl;
return 1;
}
//******** ***********************
//
//
struct node
{
int data;
node *next;
}Node;
//
struct dnode
{
int data;
dnode *left;
dnode *right;
}Dnode;
//
struct node * Initlist(int n)
{
node *head;
head=(node*)malloc(sizeof(node));
head->next=NULL;
head->data=0;
node *p=head;
int data=0;
int i=0;
while(i<n)
{
node *L;
L=(node*)malloc(sizeof(node));
cin>>data;
p->next=L;
L->data=data;
p=L;
i++;
}
p->next=NULL;
return head;
}
//
void puts(struct node *head)
{
node * p=NULL;
for(p=head->next;p!=NULL;p=p->next)
cout<<p->data<<" ";
cout<<endl;
}
//
// ，P ，r ，q 。
void Reverselist(struct node *head)
{
node *p=head->next;
node *q=NULL;
node *r=NULL;
while(p)
{
r=q;
q=p;
p=p->next;
q->next=r;
}
head->next=q;
}
// ， ， ，
// 。
// A，B ， C，
int mubble(node *ListA,node *ListB)
{
node *p=NULL;
p=ListA->next;
node *q=NULL;
q=ListB->next;
node *c=NULL;
while(p->next!=NULL&&q!=NULL)
{
while(p->data<=q->data&p!=NULL)
{
c=p;
if(p->next!=NULL)
p=p->next;
}
c->next=q;
while(q->data<=p->data&&q!=NULL)
{
c=q;
if(q->next!=NULL)
q=q->next;
}
c->next=p;
}
c->next=q;
return 1;
}
// string 、 、
class String
{
public:
String(const char *str=NULL);
String(const String &other);
~String();
String & operator =( const String &other);
private:
char *data;
};
String::String(const String &other)
{
int len=strlen(other.data);
data=new char(len+1);
strcpy(data,other.data);
}
String::~String()
{
delete [] data;
}
String & String::operator =( const String &other)
{
if(this == &other)
return *this;
delete [] data;
int length = strlen(other.data);
data = new char[length+1];
strcpy(data, other.data);
return *this;
}
void main()
{
// char instr[]="ppddsdpp";
// char neinstr[]="5 - 15";
// int n=sizeof(instr);
//char outstr[100]={ };
//char aa[]="hello";
//char cstr[]="a3c3hello212my221dd22www";
//stringFilter(instr,n,outstr);
//stringZip(instr,n,outstr);
//arithmetic(neinstr,n,outstr);
//cout<<aa<<endl;
//cout<<outstr<<endl;
//cout<<noutstr<<endl;
//convert(cstr,outstr);
//my_word(cstr,outstr);
//cout<<outstr<<endl;
/*int a=121;
bool f=isPrimNumber(a);
if(f)
cout<<" "<<endl;
else
cout<<" "<<endl;*/
/*int ary[6]={4,4,21,1,2,23};
int k=func(ary,6);
cout<<k;*/
/*int i=12344221;
bool f=isPlalindromeNumber(i);
if(f)
cout<<" "<<endl;
else
cout<<" "<<endl;
getPrim(100); */
//int a=230;
//cout<<func(a)<<endl;
//int a[10]={2,34,5,22,212,32,43,12,9,12};
//InsertionSort(a,10);
//SelectSort(a,10);
//BubleSort(a,10);
//Qsort(a,0,9);
//for(int i=0;i<10;i++)
// cout<<a[i]<<" ";
/*int b=5;
int * const p=&b;
int a=12;
int * const r=&b;
const int * p=&a;
int k=6;
//p=&k;
b=k;
cout<<b<<endl;*/
//char *ss="hello";
//int p=sizeof(ss);
//int q=strlen(ss);
//cout<<p<<q;
//int a=0;
//char b='a';
//char str[]="1000";
//int k=parseInt(str,2);
//cout<<k;
//lag(100);
struct node * L1=Initlist(5);
struct node * L2=Initlist(7);
puts(L1);
puts(L2);
mubble(L1,L2);
//Reverselist(L1);
puts(L1);
system("pause");
}