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;
}
第一题第二题不会做真的建议重新学一遍C,但凡好好写作业的都不至于写不出来吧
教教
教教
花花太强了