c++解题方法与技巧.doc

第 35 题  ：  明明的随机数
(时间限制为：500毫秒)
    明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式 Input Format
输入文件有2行，第1行为1个正整数，表示所生成的随机数的个数：N
第2行有N个用空格隔开的正整数，为所产生的随机数。
输出格式 Output Format
输出文件也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
样例输入 Sample Input
6
9 8 8 12 10 10
样例输出 Sample Output
4
8 9 10 12
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
int n,i,c;
cin>>n;
set<int>v;//把数一个个插入到v中
set<int>::iterator it//访问
for(i=0;i<n;i++)
{
cin>>c;
v.insert(c);//把c插入到v中
}
n=v.size();
cout<<n<<endl;
for(it=v.begin();it!=v.end();it++)
{
cout<<(*it)<<" ";//用指针访问
}
cout<<endl;
return 0;

}
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{I nt i,n,a[100];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);//从小到大排序
for(i=0;i<n;i++)
cout<<a[i]<<' ';
}

int compar(int a,int b)
{
return a<b?a:b;
}
sort(a,a+n,compar);

a的b次方对c求余 当数很大的时候有公式（ab%c=ab-1*a%c%c ）所以有
t=a;
for(j=2;j<=b;j++)
a=(a%c)*t;
cout<<a%c<<endl;
cin.getline用法{例题2126（统计难题）}
此函数是按行读取,其语法为:cin.getline(字符指针,字符个数N,结束符);
　　功能是：一次读取多个字符(包括空白字符），直到读满N-1个，或者遇到指定的结束符为止(默认的是\0)。
　　例:
　　#include <iostream>
　　using namespace std;
　　void main()
　　{
　　char a[10];
　　cin.getline(a,10);
　　for(int i=0;i<10;i++)
　　{
　　cout<<a[i]<<" ";
　　}
　　}
　　输入:1234567890123
　　输出:1 2 3 4 5 6 7 8 9 _ （第10位为空白字符'\0'）

C语言中memset函数详解
功 能: 将s所指向的某一块内存中的每个字节的内容全部设置为ch指定的ASCII值,

　　块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作

　　用 法: void *memset(void *s, char ch, unsigned n);

　　程序例:

　　#include <string.h>

　　#include <stdio.h>

　　#include <memory.h>

　　int main(void)

　　{

　　char buffer[] = "Hello world\n";

　　printf("Buffer before memset: %s\n", buffer);

　　memset(buffer, '*', strlen(buffer) );

　　printf("Buffer after memset: %s\n", buffer);

　　return 0;

　　}

　　输出结果：

　　Buffer before memset: Hello world

　　Buffer after memset: ***********

memset函数详细说明
　　1。void *memset(void *s,int c,size_t n)

　　总的作用：将已开辟内存空间 s 的首 n 个字节的值设为值 c。

　　2。例子

　　main(){

　　char *s="Golden Global View";

　　clrscr();

　　memset(s,'G',6);//貌似这里有点问题//

　　printf("%s",s);

　　getchar();

　　return 0;

　　}　

　　【这个问题相当大，程序根本就运行不下去了，你这里的S志向的是一段只读的内存，而你memset又试图修改它，所以运行时要出错，修改办法char *s修改为char s[]】

　　3。memset() 函数常用于内存空间初始化。如：

　　char str[100];

　　memset(str,0,100);

　　4。memset()的深刻内涵：用来对一段内存空间全部设置为某个字符，一般用在对定义的字符串进行初始化为‘memset(a, '\0', sizeof(a));

　　memcpy用来做内存拷贝，你可以拿它拷贝任何数据类型的对象，可以指定拷贝的数据长度；例：char a[100],b[50]; memcpy(b, a, sizeof(b));注意如用sizeof(a)，会造成b的内存地址溢出。

　　strcpy就只能拷贝字符串了，它遇到'\0'就结束拷贝；例：char a[100],b[50];strcpy(a,b);如用strcpy(b,a)，要注意a中的字符串长度（第一个‘\0’之前）是否超过50位，如超过，则会造成b的内存地址溢出。

　　5.补充：某人的一点心得

　　memset可以方便的清空一个结构类型的变量或数组。

　　如：

　　struct sample_struct

　　{

　　char csName[16];

　　int iSeq;

　　int iType;

　　};

　　对于变量

　　struct sample_strcut stTest;

　　一般情况下，清空stTest的方法：

　　stTest.csName[0]='\0';

　　stTest.iSeq=0;

　　stTest.iType=0;

　　用memset就非常方便：

　　memset(&stTest,0,sizeof(struct sample_struct));

　　如果是数组：

　　struct sample_struct TEST[10];

　　则

　　memset(TEST,0,sizeof(struct sample_struct)*10);

　　6。strcpy

　　原型：extern char *strcpy(char *dest,char *src);

　　用法：＃i nclude

　　功能：把src所指由NULL结束的字符串复制到dest所指的数组中。

　　说明：src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。

　　返回指向dest的指针。

　　memcpy

　　原型：extern void *memcpy(void *dest, void *src, unsigned int count);

　　用法：＃i nclude

　　功能：由src所指内存区域复制count个字节到dest所指内存区域。

　　说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针。

　　memset

　　原型：extern void *memset(void *buffer, int c, int count);

　　用法：＃i nclude

　　功能：把buffer所指内存区域的前count个字节设置成字符c。

说明：返回指向buffer的指针。
负权数
#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
   int n,r,a[100],p,j;
   while(scanf("%d%d",&n,&r)!=EOF)
   {
           int n1=abs(n);
         int r1=abs(r);
           int i=0;
          memset(a,0,sizeof(a));
          //通过连除求余得到|n|的|r|进制形式
          while(n1>0)
         {
               a[i]=n1%r1;
                n1/=r1;
                i++;
          }
          //以下将|n|的|r|进制形式转化为n的r进制形式。
         if(n>0)
          p=1;
          else p=0; //n<0
          i--;
          while(p<=i)
          {
              if(a[p]>0)
              {
                    a[p+1]++; //向a[p+1]位进1
                     j=p+1;
                    while(a[j]>=r1) //修改
                     {
                        a[j]-=r1;
                         j++;
                         a[j]++;
                    }
                    if(j>i) //如果长度变长了
                    {
                         i=j;    
                    }
                     a[p]=r1-a[p];
                }
                p+=2;
          }
          for(j=i;j>=0;j--)
         {
               if(a[j]<10)
                      printf("%d",a[j]);
               else printf("%c",a[j]-10+'A');
          }
         printf("\n");
    }
    return 0;
}

最大公约数
　　最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。
　　例如，12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数。
　　两个整数的最大公约数主要有两种寻找方法：
　　* 两数各分解质因子，然后取出同样有的项乘起来
　　* 辗转相除法（扩展版）
　　和最小公倍数（lcm）的关系：gcd(a, b)×lcm(a, b) = ab
　　两个整数的最大公因子可用于计算两数的最小公倍数，或分数化简成最简分数。
　　两个整数的最大公因子和最小公倍数中存在分配律：
　　* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
　　* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
　　在座标里，将点(0, 0)和(a, b)连起来，通过整数座标的点的数目（除了(0, 0)一点之外）就是gcd(a, b)。
　　//GDC 分解因素法
　　#include<iostream>
　　using namespace std;
　　int main()
　　{
　　int s,x,y,i;
　　i=2;s=1;
　　cin>>x,y;
　　while(i<x)
　　{
　　if((x%i==0)&&(y%i==0))//i是其因子
　　{s*=i;//符合条件的因子累积
　　x/=i;
　　y/=i;
　　}
　　else i=i+1;//测试试除数
　　}
　　cout<<"GCD is"<<s<<endl;
　　return 0;
　　}
　　虽然可以 计算 但有时结果不是很理想
　　//GDC 辗转相除法
　　#include<iostream>
　　using namespace std;
　　int main()
　　{
　　int m,n,r;
　　cin>>m,n;
　　if(m<n)
　　{int t;
　　t=n;n=m;m=t;}
　　else{
　　do{
　　r=m%n;
　　m=n;
　　n=r;
　　}while(r);}
　　cout<<"GCD is"<<m;
　　return 0;
　　}
　　//work out gcd with sub
　　#include <iostream>
　　using namespace std;
　　int main()
　　{
　　int x,y,a,b;
　　cin>>x>>y;
　　a=x;
　　b=y;
　　while(a!=b)
　　if(a>b)
　　a-=b;
　　else
　　b-=a;
　　cout<<"Gcd is"<<a;
　　return 0;
　　}
　　//递归法
　　#include <iostream>
　　using namespace std;
　　int gcd(int x,int y)
　　{int Gcd;
　　if(x%y==0)
　　Gcd=y;
　　else
　　Gcd=gcd(y,x%y);
　　return Gcd;
　　}
　　int main()
　　{
　　int a,b;
　　cin>>a>>b;
　　cout<<"Gcd is the hope of our people"<<gcd(a,b);
　　return 0;
　　}
　　#include <iostream>
　　using namespace std;
　　class Max_gcd
　　{
　　public:
　　int gcd1(int m,int n);
　　int gcd2(int m,int n);
　　int gcd3(int m,int n);
　　int gcd4(int m,int n);
　　private:
　　int m,n;
　　};
　　int Max_gcd::gcd1(int m,int n)
　　{
　　int d=1;
　　for(int k=2;k<=m&&k<=n;k++)
　　if(m%k==0&&n%k==0)
　　d=k;
　　return d;
　　}
　　int Max_gcd::gcd2(int m,int n)
　　{
　　int k;
　　for(k=(m>n ? n:m);m%k!=0||n%k!=0;k--)
　　;
　　return k;
　　}
　　int Max_gcd::gcd3(int m,int n)
　　{
　　int r;
　　do{
　　r=m%n;
　　m=n;
　　n=r;
　　}while(r);
　　return m;
　　}
　　int Max_gcd::gcd4(int m,int n)
　　{
　　int r;
　　if(n==0) return m;
　　for(r=m%n;r!=0;r=m%n)
　　{
　　m=n;
　　n=r;
　　}
　　return n;
　　}
　　int main()
　　{
　　int x,y;
　　int j=1;
　　char choice;
　　Max_gcd gcd;
　　while(j)
　　{
　　cout<<"-----------------------------------------------"<<endl;
　　cout<<" 多种方法求最大公约数："<<endl;
　　cout<<" 试除法求最大公约数a："<<endl;
　　cout<<" 从某个大数求最大公约数b："<<endl;
　　cout<<" 辗转相除法求最大公约数c："<<endl;
　　cout<<" 利用殴几里得算法和循环结构求最大公约数d："<<endl;
　　cout<<"------------------------------------------------"<<endl;
　　cout<<"\t\t请选择菜单号(a--d)：";
　　cin>>choice;
　　getchar();
　　if(choice=='a')
　　{
　　cout<<"please input m,n:"<<endl;
　　cin>>x>>y;
　　cout<<gcd.gcd1(x,y)<<endl;
　　}
　　if(choice=='b')
　　{
　　cout<<"please input m,n:"<<endl;
　　cin>>x>>y;
　　cout<<gcd.gcd2(x,y)<<endl;
　　}
　　if(choice=='c')
　　{
　　cout<<"please input m,n:"<<endl;
　　cin>>x>>y;
　　cout<<gcd.gcd3(x,y)<<endl;
　　}
　　}
　　if(choice=='d')
　　{
　　cout<<"please input m,n:"<<endl;
　　cin>>x>>y;
　　cout<<gcd.gcd4(x,y)<<endl;
　　}
　　return 0;
}

例题：第 14 题    Freary序列
#include<iostream>
using namespace std;
struct Piont
{
double s;
int a;
int b;
}p[10000];
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
int main()
{
int n,i,j,l=0,t;
double q;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
if(gcd(i,j)==1)
{
p[l].s=double(j)/double(i);
p[l].a=j;
p[l].b=i;
l++;
}
for(i=1;i<l;i++)
for(j=0;j<l-i;j++)
if(p[j].s>p[j+1].s)
{
q=p[j].s;p[j].s=p[j+1].s;p[j+1].s=q;
t=p[j].a;p[j].a=p[j+1].a;p[j+1].a=t;
t=p[j].b;p[j].b=p[j+1].b;p[j+1].b=t;
}
for(i=0;i<l-1;i++)
cout<<p[i].a<<"/"<<p[i].b<<",";
cout<<p[i].a<<"/"<<p[i].b<<endl;
return 0;
}