- 前言
- 一、2021/12/28——Day1
- 二、2021/12/29——Day2
- 1.找出n个升序数组中的公共元素
- 2.给定一个n个整型元素的数组a，其中有一个元素出现次数超过n/2，求这个元素
- 三、2021/12/30——Day3
- 1.从键盘上输入字符，分别统计一下其中字母，数字，其他字符的个数；将统计的字母，数字，其他字符的个数以柱状图的形式打印。
- 2.有101个整数，其中有50个数出现了两次，1个数出现了一次， 找出出现了一次的那个数。
- 3.有102个整数，其中有50个数出现了两次，2个数出现了一次， 找出出现了一次的那两个数。
- 4.有103个整数，其中有50个数出现了两次，3个数出现了一次， 找出出现了一次的那3个数。
- 四、2021/12/31——Day4
- 五、2022/1/1——Day5
- 1.大整数加法。 实现任意范围的两个整数的加法（ 整数的范围用 int 型的变量无法表示,50位）
前言
第一周主要讲述了C语言的基础语法，内容也较为简单；但作业有几题较有挑战性，本文主要记录本周的上课内容及较为有挑战的作业，以作课后的自我总结。
一、2021/12/28——Day1
Day1讲述环境安装等写代码前各类准备。
二、2021/12/29——Day2Day2讲述数据类型、进制转换以及标准输入相关内容。
1.找出n个升序数组中的公共元素分析：只需找出两数组的公共元素，并保存在数组result中；再寻找result数组与其他数组的公共元素；直到result为空或与其他数组都比较过。就可以将问题分解为找出两个升序数组的公共元素问题。
找出两个升序数组a,b的公共元素：用两指针pointA和pointB分别指向a,b的首个元素。若a[pointA] < b[pointB]，pointA+1；若a[pointA] = b[pointB]，将a[pointA]存储至result数组中；若a[pointA] > b[pointB]，pointB+1。直至遍历完数组a或b，result数组中存储的就是a和b的公共元素。
找出两个升序数组a,b的公共元素代码如下：
//count为result数组的长度
int count = 0;
//返回值为公共元素组成的数组
int* FindPublic(int a[], int b[], int NumA, int NumB) {
int pointA = 0, pointB = 0;
int* result = (int*)malloc(sizeof(int) * NumA);
count = 0;
while (pointA < NumA && pointB < NumB) {
if (a[pointA] < b[pointB])
pointA++;
else if (a[pointA] > b[pointB])
pointB++;
else {
result[count] = a[pointA];
pointA++;
pointB++;
count++;
}
}
return result;
}
找出n个升序数组的公共元素代码如下：
result = FindPublic(a , b , numA , numB);
for(int i = 0; i < n - 2;i++){
numA = count;
if(numA == 0){
break;
}
printf("Please Input the arrLen:");
scanf("%d", &numB);
printf("Please Input the %dth array:", i);
for(int j = 0; j < numB; j++){
scanf("%d", &b[j]);
}
result = FindPublic(result, b, count, numB);
}
2.给定一个n个整型元素的数组a，其中有一个元素出现次数超过n/2，求这个元素
分析：
思路一：先排序，再寻找。但排序效率很低；
思路二：通过哈希表保存不同元素出现次数。只需要遍历一次数组a，遍历一次哈希表。时间复杂度O(n)；空间复杂度和数组a中的不同元素个数有关；
思路三：利用选举时候选人思想；若存在票数大于n/2的候选人，则该候选人的票数比其他候选人的票数之和还要多。
candidate存储当前占优势的候选人，prior代表当前候选人的优势为多少；设置candidate的初始值为a[0]，prior的初始值为0；从a[0]开始遍历整个数组。
遍历结束的条件为：（1）遍历完整个数组 或 （2）prior的值大于 n/2 。
若当前得到的数组元素a[k] != candidate，则原候选人的优势变小，prior-1；否则prior+1。当prior=-1时，说明当前候选人已失去票数优势，则更新候选人candidate=a[k]，并设置prior=1。
该方法只需要遍历一边数组a，且只需要常数级的额外空间，时间复杂度为O(n)，空间复杂度为O(1)。
代码如下：
void Find_candidate() {
int* A, NumA;
int candidate, prior;
printf("Please Input the arrlen:");
scanf("%d", &NumA);
A = (int*)malloc(sizeof(int) * NumA);
printf("Please Input the arry elem:");
for (int i = 0; i < NumA; i++)
scanf("%d", &A[i]);
int i = 0;
prior = 0;
candidate = A[0];
while (i < NumA && prior <= NumA / 2) {
if (A[i] == candidate) {
prior++;
}
else {
prior--;
if (prior == -1) {
candidate = A[i];
prior = 1;
}
}
i++;
}
if (prior >= 1) {
printf("The Element is %dn", candidate);
}
else {
printf("No such Elementn");
}
}
三、2021/12/30——Day3
Day3讲述各类输入输出函数（scanf、getchar、printf、putchar）；讲述各类运算符的运算方式、优先级；讲述选择循环语法。
1.从键盘上输入字符，分别统计一下其中字母，数字，其他字符的个数；将统计的字母，数字，其他字符的个数以柱状图的形式打印。
这题暂时不会，只会统计各类字符个数，如何打印还没讲。等待更新~
分析：利用异或 *** 作：两相同的数字异或结果为0；任何数字a与0异或的结果都是它本身。将数组中的数依次异或，得到的结果就是只出现了一次的那个数。
代码如下：
void AppearOnce() {
int a[101];
int num = 0;
printf("Please Enter 101 Numbers:");
for (int i = 0; i < 101; i++) {
scanf("%d", &a[i]);
num = num ^ a[i];
}
printf("Number %d is the only Appear Oncen", num);
}
3.有102个整数，其中有50个数出现了两次，2个数出现了一次， 找出出现了一次的那两个数。
分析：将102个数进行分堆，将两个只出现了一次的数a，b分到两堆中。
分成什么样的两堆：将x，y两数分在不同的两堆heapA，heapB中，并且令同样的数分在同一堆中。就可以将该问题分解为两个问题21。
如何分堆：
- 将数组a依次异或，得到数m。数m实质是由x和y相互异或得到的，且m != 0；
- 根据异或的规律，m在二进制表示下“1”所在的位，x和y对应的值是不同的。例如：x = (1001 0010)B，y = (1010 1010)B，m = x ^ y = (0011 1000)B，在二进制下，m的第4,5,6三位为1，即证明x和y的4,5,6三位互不相同；
- 因此只需要找到m的最低位“1”所在，根据数组a中各个数在该位的值进行分堆。就能够实现：（1）将所有相同的数分在同一堆；（2）将x和y分在不同堆
代码如下：
void AppearOnce() {
int a[102];
int num = 0;
printf("Please Enter 102 Numbers:");
for (int i = 0; i < 102; i++) {
scanf("%d", &a[i]);
num = num ^ a[i];
}
//寻找num中最低位的1
int cmp = 1;
while ( !(cmp & num)) {
cmp = cmp << 1;
}
int num1 = 0, num2 = 0;
for (int i = 0; i < 102; i++) {
if (a[i] & cmp) {
num1 = num1 ^ a[i];
}
else {
num2 = num2 ^ a[i];
}
}
printf("Number %d and %d are the only Appear Oncen", num1, num2);
}
4.有103个整数，其中有50个数出现了两次，3个数出现了一次， 找出出现了一次的那3个数。
分析：将103个数分成两堆
分成什么样的两堆：将x，y，z两数分在不同的两堆heapA，heapB中，并且令同样的数分在同一堆中。其中使得一堆中存在x，y，z中的两个数，另一堆中存在x，y，z中的一个数。就可以将该问题分解为一个问题21，一个问题32。
如何分堆（暴力分堆，最多分堆32次）：
- 从count = 1开始，将数组a中 a&count 结果为真的分到heapA，a&count 结果为假的数分到heapB。随后将count左移一位。
- 由于将奇数个数字分为两堆，必定存在一堆个数为偶数个，另一堆的数个数为奇数个。接下来需在偶数堆中判断，是否将x，y分入此堆。判断方法为：将偶数堆中的所有数依次异或，若得到结果为0，说明x，y，z都在奇数堆中，需要将count左移一位，重新进行分堆。
代码如下（只包含分堆代码）：
#define MaxSize 103
void Divide() {
int n, lenA, lenB;
int a[MaxSize], Heapa[MaxSize], Heapb[MaxSize];
printf("Please Enter tht arrNum:");
for (int i = 0; i < MaxSize; i++) {
scanf("%d", &a[i]);
}
int count = 1;
for (int i = 0; i < 32; i++) {
lenA = 0;
lenB = 0;
int judge1 = 0, judge2 = 0;
for (int j = 0; j < MaxSize; j++) {
if (a[j] & count) {
Heapa[lenA] = a[j];
judge1 = judge1 ^ a[j];
lenA++;
}
else {
Heapb[lenB] = a[j];
judge2 = judge2 ^ a[j];
lenB++;
}
}
if (judge1 != 0 && judge2 != 0) {
break;
}
count = count << 1;
}
}
四、2021/12/31——Day4
Day4讲述一维数组、二维数组、字符数组及其性质。跨年夜题较为简单，非常银杏化。
五、2022/1/1——Day5Day5讲述指针、指针的传递及性质；在函数中的形参和实参。
1.大整数加法。 实现任意范围的两个整数的加法（ 整数的范围用 int 型的变量无法表示,50位）分析：用字符串存储大整数a，b，再从低位到高位依次相加，存入空字符串c中即可（注意c中存储的内容和结果相反，应该将c翻转，从而得到正确答案）
#define _CRT_SECURE_NO_WARNINGS #include#include //将a[left]到a[right]内容翻转 void Flip(char a[], int left, int right) { char c; while (left < right) { c = a[left]; a[left] = a[right]; a[right] = c; left++; right--; } } int main() { while (1) { char a[51], b[51],sum[52]; printf("请输入大整数a（不超过50位）:"); gets(a); printf("请输入大整数b（不超过50位）:"); gets(b); int lenA = strlen(a); int lenB = strlen(b); int i = lenA - 1; int j = lenB - 1; int add = 0; int numA, numB; //c=0代表无低位进位，c=1代表有低位进位 int c = 0; while (i >= 0 && j >= 0) { numA = a[i] - '0'; numB = b[j] - '0'; int k = numA + numB + c; if (k >= 10) { c = 1; sum[add] = k - 10 + '0'; } else { sum[add] = k + '0'; c = 0; } i--; j--; add++; } while (i >= 0) { numA = a[i] - '0'; int k = numA + c; if (k >= 10) { c = 1; sum[add] = k - 10 + '0'; } else { c = 0; sum[add] = k + '0'; } i--; add++; } while (j >= 0) { numB = b[j] - '0'; int k = numB + c; if (k >= 10) { c = 1; sum[add] = k - 10 + '0'; } else { c = 0; sum[add] = k + '0'; } j--; add++; } sum[add] = c == 0 ? c : c + '0'; if (c == 1) { add++; sum[add] = 0; } Flip(sum, 0, add - 1); printf("a+b="); puts(sum); } return 0; }
思考：是否可以参照组成原理中CLA四位加法器，不需要从低到高一位一位生成进位位，而是一次性生成四位进位位？
有2N+1个整数，其中有N个数出现了两次，1个数出现了一次， 找出出现了一次的那个数。 ↩︎ ↩︎
有2N+2个整数，其中有N个数出现了两次，2个数出现了一次， 找出出现了一次的那两个数。 ↩︎
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）