C程序设计基础第三次月考上机

1055. 集合交集

int Intersection(int s1[],int n1,int s2[],int n2,int r[]){
/* 
   PreCondition: 集合元素存放在s1,s2中；n1, n2分别为两个集合大小
   PostCondition: s1和s2的交集存放在r中，元素按由小到大存放；返回交集中元素个数
*/
}

int main()
{
    int n1,n2,i;
    int s1[N],s2[N],r[N];

    scanf("%d",&n1);
    for(i=0;i<n1;i++)
        scanf("%d",&s1[i]);

    scanf("%d",&n2);
    for(i=0;i<n2;i++)
        scanf("%d",&s2[i]);

    int n=Intersection(s1,n1,s2,n2,r);
    for(i=0;i<n;i++)
        printf("%d ",r[i]);
    putchar('\n');

    return 0;
}

题解

签到题，这题要是不会做建议重学。

代码

#include <stdio.h>
#include <stdlib.h>
#define N 100

int cmp(const void* a, const void *b) 
{
    long long c = *(int*)a-*(int*)b;
    if(c>0) return 1;
    if(c<0) return -1;
    return 0;
}

int Intersection(int s1[],int n1,int s2[],int n2,int r[])
{
    int count = 0;
    int i = 0, j = 0;
    for(i = 0; i < n1; i++){
        for(j = 0; j < n2; j++){
            if(s1[i]==s2[j]){
                r[count] = s1[i];
                count++;
                break;
            }
        }
    }
    if(count)
        qsort(r,count,sizeof(int),cmp);
    return count;
}

int main()
{
    int n1,n2,i;
    int s1[N],s2[N],r[N];

    scanf("%d",&n1);
    for(i=0;i<n1;i++)
        scanf("%d",&s1[i]);

    scanf("%d",&n2);
    for(i=0;i<n2;i++)
        scanf("%d",&s2[i]);

    int n=Intersection(s1,n1,s2,n2,r);
    for(i=0;i<n;i++)
        printf("%d ",r[i]);
    putchar('\n');

    return 0;
}

1056. 数字猜想

一个正整数x，如果是奇数就乘以3再加1；如果是偶数就除以2。这样经过若干个次操作，最终会回到1。

例如 x=3 时，3 * 3 + 1 = 10, 10/2=5, 5*3+1=16, 16/2=8, 8/2=4, 4/2=2, 2/2=1。

输入一个正整数，输出经过上述操作回到1的路径。
1<x<=100

题解

签到题，不会做重学。
定义一个函数f能大大简化主函数。

代码

#include <stdio.h>
#include <stdlib.h>

int f(int a){
    if(a%2==1)
        return a*3+1;
    else
        return a/2;
}

int main()
{
    int n;
    scanf("%d",&n);

    while(n!=1){
        printf("%d ",n);
        n=f(n);
    }

    printf("1\n"); 

    return 0;
}

1057. SortIntegers

对 n(<=1000 >1) 个正整数组成的数组按以下顺序排序：

按正整数二进制表示中1 的位数的降序排序，1 的位数相同的数按数本身值的升序排序。

使用 qsort 定义函数 Sort

void Sort(unsigned *p, unsigned n);
/* PreCondition:  
          p points to an array with n unsigned integers
    PostCondition: 
          array is sorted satisfying to the specification
*/

main函数如下：

int main()
{ unsigned n,i,a[1000];  scanf("%u",&n);
  for (i=0;i<n;i++) scanf("%u",a+i);   Sort(a,n);
  for (i=0;i<n;i++) printf("%u%c",a[i],i!=n-1?' ':'\n');
  return 0;
}

题解

这题的数据很坑，两个unsigned相减得到的结果肯定无法存放在int类型里面，也就无法直接返回差值。
因此我们习惯性将差值缩小到1和-1，也就是只看正负，不管具体的值是什么。
可以留意以下cmp的写法，我代码中的写法不是最好的写法，对于longlong范围的整数仍然可能出现数据溢出。思考一下怎么写更好。

代码

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b){
    int A = getOne(*(unsigned*)a);
    int B = getOne(*(unsigned*)b);
    unsigned x = *(unsigned*)a;
    unsigned y = *(unsigned*)b;

    if(A!=B)
        return (B-A)>0?1:-1;
    else{
        if(x>y) return 1;
        if(x<y) return -1;
    }
}

int getOne(unsigned a){
    int count = 0;
    while(a){
        if(a%2==1)
            count++;
        a /= 2;
    }
    return count;
}

void Sort(unsigned *p, unsigned n){
    qsort(p,n,sizeof(unsigned),cmp);
}
int main()
{ unsigned n,i,a[1000];  scanf("%u",&n);
  for (i=0;i<n;i++) scanf("%u",a+i);   Sort(a,n);
  for (i=0;i<n;i++) printf("%u%c",a[i],i!=n-1?' ':'\n');
  return 0;
}

1058. SortPoints

对一个平面坐标系统中的 n 个点按以下顺序排序：

按在坐标系统中点与原点之间的曼哈顿距离从大到小排序。距离相同时按坐标 的值从小到大排序， 的值也相等时按坐标 的值从小到大排序。

第1行是一个整数 n
后面 n 行，每行包含空格分隔的两个整数 x 和 y 表示一个点的坐标
输出排序后点的坐标。点的格式为(x,y)

题解

这题我个人觉得最好的做法，就是使用结构体数组。
定义一个Point结构体，一个返回曼哈顿距离的方法，一个打印Point的函数。
这题其实使用面向对象编程思想是最简单的。
接下来我用伪代码说明。

Point{
    long long x,y; //横纵坐标
    long long d(){} //返回曼哈顿距离的方法，使用自己的x和y数据
    void print(){} //按照某种格式输出自己坐标的方法
}

对于每一个Point的对象，需要上述代码中写的数据+方法，也就是上述数据+方法构成了一个完整的类型。
但对于C语言，显然不需要按照class的方式定义方法，我们只需要定义结构体，然后定义符合结构体类型的函数就行了。

代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 

typedef struct point{
    long long x;
    long long y;
}Point; 

unsigned long long d(Point a){
    return fabs(a.x)+fabs(a.y);
}

int cmp(const void* a, const void* b){
    Point X = *(Point*)a;
    Point Y = *(Point*)b;
    unsigned long long A = d(*(Point*)a);
    unsigned long long B = d(*(Point*)b);

    if(A!=B)
        return B>A?1:-1;
    else{
        if(X.x!=Y.x) return X.x>Y.x?1:-1;
        else{
            if(X.y!=Y.y) return X.y>Y.y?1:-1;
        }
    }
}

void myPrint(Point a){
    printf("(%lld,%lld)",a.x,a.y);
} 

int main()
{
    int n;
    scanf("%d",&n);
    Point arr[101];
    int i;
    for(i = 0; i < n; i++)
        scanf("%lld%lld",&(arr[i].x),&(arr[i].y));
    qsort(arr,n,sizeof(Point),cmp);
    for(i = 0; i < n; i++)
        myPrint(arr[i]);
    return 0;
}