最小公倍数和最大公因数
C语言最大公约数和最小公倍数:http://c.biancheng.net/view/562.html
#include <stdio.h>
void main()
{
int gongyue(int a, int b);
int d;
int num1, num2;
printf("输入2个正整数:\n");
scanf_s("%d %d", &num1, &num2);
d = gongyue(num1, num2);
printf("最大公约数为:%d\n", d);
printf("最小公倍数为:%d\n", (num1 * num2 / d));
}
- Stein算法
Stein算法由J. Stein 1961年提出,这个方法也是计算两个数的最大公约数。
Stein算法:https://baike.baidu.com/item/Stein%E7%AE%97%E6%B3%95
Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。
对两个正整数 x>y :
1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 );
2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 );
2.x奇y偶 gcd( x,y ) = gcd( x,y/2 );
3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 );
5.gcd( x,x ) = x ,退出条件。
计算机原理与基础 —— C语言中的左移与右移:https://blog.csdn.net/weixin_42167759/article/details/85624722
C语言位运算符:http://c.biancheng.net/view/288.html
- 非递归实现:
int divisor(int x, int y)
{
int factor = 0;
int temp;
if (x < y) //比较大小 x存储大的 y存储小的
{
temp = x;
x = y;
y = temp;
}
if (0 == y)
{
return 0;
}
while (x != y)
{
if (x % 2 != 0)
{/*当x为奇数时 */
if (y % 2 != 0)
{/* 当x和y都是奇数时 */
y = (x - y) >> 1;
x -= y;
}
else
{/* 当x为奇数 y为偶数时 */
y >>= 1;
}
}
else
{/* 当x为偶数时 */
if (y % 2 != 0)
{/* 当x为偶数 y为奇数时 */
x >>= 1;
if (x < y)
{
temp = x;
x = y;
y = temp;
}
}
else
{/* 当x和y都为偶数时 */
x >>= 1;
y >>= 1;
++factor;
}
}
}
return (x << factor);
}
- 递归实现:
int gcd(int u, int v)
{
if (u == 0) return v;
if (v == 0) return u;
if (u % 2 == 0) // u是偶数
{
if (v % 2 != 0) //u是偶数 v是奇数
return gcd(u >> 1, v);
else // u和v都是偶数
return gcd(u >> 1, v >> 1) << 1;
}
if (v % 2 == 0) // u是奇数 v是偶数
return gcd(u, v >> 1);
// u和v都是奇数
if (u > v)
return gcd((u - v) >> 1, v);
return gcd((v - u) >> 1, u);
}
- 更相减损法
更相减损术:https://baike.baidu.com/item/%E6%9B%B4%E7%9B%B8%E5%87%8F%E6%8D%9F%E6%9C%AF
可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。
(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。
如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,
一直到减数与差相等为止,用这个相等的数字来约分。
int gongyue(int a, int b)
{
int temp = 1, n = 0;
while (a % 2 == 0 && b % 2 == 0)//判断a、b能被多少个2整除
{
a = a / 2;
b = b / 2;
n++;//每次整除后记一次次数
}
while (1)
{
if (a < b)//判断a、b的大小,默认a大b小
{
temp = a;
a = b;
b = temp;
}
temp = a - b;//大的减去小的,更相减损大法!
if (b == temp)//当减数等于差的时候,跳出循环《中途结束循环》
break;
a = b;//若没判断出结束,则继续更相减损的赋值
b = temp;
}
for (int i = 1; i <= n; i++)
{
temp = temp * 2;//约掉几个2乘回去
}
// temp = temp<<n;
//左移2位之后变成 000...0100,也就是10进制的4,所以说左移1位相当于乘以2,那么左移n位就是乘以2的n次方了
return temp;
}
- 穷举法(枚举法)
穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:
从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。
int gongyue(int a, int b)
{
int temp;//定义穷举开始的变量
temp = (a < b) ? a : b;//将较小的值赋给穷举变量
while (temp > 0)//穷举变量最小将自减到1,写>0即可
{
if (a % temp == 0 && b % temp == 0)
break;//直到找到一个数能同时被a、b整除,即为最大公因数(由于自减,因此是最大的公因数)
temp--;//不能被整除的话则自减继续穷举循环
}
return temp;//将最大公因数返回到主函数
}
- 期末复习题中输出两个数的最大公因数-程序填空题-辗转相除法
欧几里得算法(辗转相除法):https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
int gongyue(int a, int b)
{
int temp;
while (b)//当余数为0时结束
{
temp = a % b;//temp取余
a = b;//将除数变为被除数
b = temp;//将余数变为除数
}
return a;
}
- 同样的原理使用递归函数实现(代码更简短)
int gongyue(int a, int b)
{
if (a % b == 0)
return b;
else
return gongyue(b, a % b);
}
素数
- 期末复习题中输出100(n)以内的素数-程序填空题
C语言判断素数(求素数)(两种方法):http://c.biancheng.net/view/498.html
思路1:因此判断一个整数m是否是素数,只需把 m 被 2 ~m - 1 之间的每一个整数去除,如果都不能被整除,那么 m 就是一个素数。
思路2:另外判断方法还可以简化。m 不必被 2 ~m - 1 之间的每一个整数去除,只需被 2 ~ 根号m之间的每一个整数去除就可以了。如果 m 不能被 2 ~ 根号m间任一整数整除,m 必定是素数。
原因:因为如果 m 能被 2 ~m - 1 之间任一整数整除,其二个因子必定有一个小于或等于根号m ,另一个大于或等于根号m。
#include <stdio.h>
#include <math.h>
void main()
{
int n, i, k;
for (n = 2; n <= 100; n++)
{
k = sqrt(n);//开平方根可以缩小需要检索的范围
for (i = 2; i <= k; i++)
if (n % i == 0) break;
if (i > k) printf(" %d", n);
}
}
- 刷洛谷时遇到的题-判断范围内的素数
#include<stdio.h>
int main()
{
int m, n;
int sum = 0;
scanf_s("%d %d", &m, &n);
int i, j;
int k, l = 0;
if (m == 1)m = 2;
for (i = m; i <= n; i++)
{
for (j = 2; j < i; j++)
{
k = i % j;
if (k == 0)break;
}
if (j == i)//if判断里"=="的问题
{
sum += i;
l++;
}
}
printf("%d~%d之间的素数之和为:%d\n素数个数为:%d", m, n, sum, l);
}
- 之前自己写过的改良版本
#include<stdio.h>
int panduan(int a)
{
int i;
int p;
for (i = 2; i <= a; i++)//这里需要<=,否则素数条件不会成立
{
p = a % i;
if (i == a)//需要"=="
{
printf("该数是素数"); break;
}
if (p == 0)
{
printf("该数不是素数"); break;
}
}
}
int quan()
{
int p;
int i, j;
printf("1000内的素数有:\n");
for (j = 2; j < 1000; j++)
{
for (i = 2; i < 1000; i++)
{
p = j % i;
if (p == 0)
{
break;
}
}
if (i >= j)
{
printf("%d ", j);
}
}
}
int main()
{
int a;
quan();
printf("\n请输入一个需要判断的数:");
scanf_s("%d", &a);
panduan(a);
}
课本p302,成绩排序-选择排序
C语言选择排序算法:http://c.biancheng.net/view/531.html
选择排序法动图演示:https://www.runoob.com/w3cnote/selection-sort.html
选择排序法和冒泡排序法:https://blog.csdn.net/live_wyq/article/details/45154265
冒泡排序算法(超级详细):http://c.biancheng.net/view/6506.html
#include<stdio.h>
struct Student
{
int num;
char name[20];
float score;
};
int main()
{
struct Student stu[5] =
{
{10101,"Zhang",78},
{10103,"Wang",98.5},
{10106,"Li",86},
{10108,"Ling",73.5},
{10110,"Sun",100}
};
struct Student temp;
const int n = 5;
int i, j, k;
printf("排序为:\n");
/********************选择排序********************/
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (stu[j].score > stu[k].score)
{
k = j;
}
}
temp = stu[k];
stu[k] = stu[i];
stu[i] = temp;//可放在第二层for循环里也可以放在第一层for循环里(思路上应该都没错,感觉放在第一层里会好理解一些)
}
/********************冒泡排序********************/
for (i = 0; i < n; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (stu[j + 1].score > stu[j].score)
{
temp = stu[j + 1];
stu[j + 1] = stu[j];
stu[j] = temp;
//i++;
}
}
}
for (i = 0; i < n; i++)
{
printf("%6d %8s %6.2f\n", stu[i].num, stu[i].name, stu[i].score);
}
printf("\n");
return 0;
}
实验报告三-(4)-删除字符串中指定的字符以及对数组溢出的处理
#include<stdio.h>
char newcopy(char* n, char* o)
{
int i = 0, j = 0, t = 0;//定义三个需要用在指针上的变量
for (i = 0; *(o + i) != '\0'; i++)
{
if (*(o + i) < 'a' || *(o + i) > 'z')//判断:如果该字符为非小写字母,则将该字符赋给新的字符串new中
{
*(n + t++) = *(o + i);
//C语言删除字符数组中特定的字符:http://c.biancheng.net/cpp/html/2812.html
//这算法属实令我醍醐灌顶,很简洁有效
}
else//否则将其重新指向旧数组的前列
{
*(o + j++) = *(o + i);//从头开始每增加一个需要删除(或者说不需要添加到新数组)的小写字母,往后一位一位增加
}
}
*(o + j) = '\0';//新旧数组结尾加上终止符
*(n + t) = '\0';
}
int main()
{
//char a[100] = {'A','B','C','d','E','f','g','h','i','J','K','l','M','N'};//初始化字符串
char a[100];
//数组越界及其避免方法,C语言数组越界详解:http://c.biancheng.net/view/366.html
//其实就tm给这个数组大一点的范围就好了……
char b[100];
printf("请输入需要处理的字符串:");
gets(a);//初始化字符串
char* o = a;//o指针代表指向old旧数组
char* n = b;//n指针代表指向new新数组(不能用new作为形参,new为C语言的一个特定符号)
newcopy(n, o);//传递指针
printf("删除的字母为:%s", o);//输出被删除的小写字母
printf("\n处理后的字符串为:% s", n);//输出处理后的字符串new
return 0;
}
课本p291-2-指针方法处理将字符串从小到大排序输出-传递数组指针
#include<stdio.h>
#include<string.h>
#define N 3
char d(char* d[N])
{
int i, j;
char* temp;
for (i = 0; i < N - 1; i++)
for (j = i + 1; j < N; j++)
if (strlen(d[i]) > strlen(d[j]))
{
temp = d[j];
d[j] = d[i];
d[i] = temp;
}
//C语言:使用指向指针的指针对字符串排序:https://blog.csdn.net/weixin_44779591/article/details/89840470
//(其实并没有用到指向指针的指针,但明白了怎么传递数组指针
}
int main()
{
char ptr[N][80];
char* p[N];//定义了一个指针数组,p290
char* temp;
int i, j;
for (i = 0; i < N; i++)
{
printf("请输入第%d段字符串:", i + 1);
gets(ptr[i]);
}
for (i = 0; i < N; i++) p[i] = ptr[i];//将指针数组的三个指针分别指向二维数组的三行
d(p);//将指针数组的值(×地址)传给形参
printf("排序后的字符串为:\n");
for (i = 0; i < N; i++) puts(p[i]);
return 0;
}
实验报告三-(2)-对二维数组指针的理解
#include<stdio.h>
int cheng(int* pa, int* pb, int* pc)
{
int(*a)[3] = pa;//使指向一维数组的指针指向main函数传递过来的三个数组首元素的地址
int(*b)[3] = pb;
int(*c)[3] = pc;
int m, n;
for (m = 0; m < 3; m++)
{
for (n = 0; n < 3; n++)
{
//*(*(c+m)+n)=*(*(a+m)+0) * *(*(b+0)+n) + *(*(a+m)+1) * *(*(b+1)+n) + *(*(a+m)+2) * *(*(b+2)+n);
//a[i][j] == p[i][j] == *(a[i]+j) == *(p[i]+j) == *(*(a+i)+j) == *(*(p+i)+j)
c[m][n] = a[m][0] * b[0][n] + a[m][1] * b[1][n] + a[m][2] * b[2][n];
//之前不用函数时写的:C[m][n] = A[m][0] * B[0][n] + A[m][1] * B[1][n] + A[m][2] * B[2][n];//对C数组进行运算
//指向指针的指针/二级指针:https://blog.csdn.net/qq_41274875/article/details/103919740
//C语言之指向一维数组的指针:https://blog.csdn.net/qq_31504597/article/details/79966023
//C语言二维数组指针(指向二维数组的指针)详解:http://c.biancheng.net/view/2022.html
}
}
printf("C数组的九个值为:\n");
for (m = 0; m < 3; m++)
{
for (n = 0; n < 3; n++)
{
printf("C[%d][%d]=%d\n", m, n, *(*(c + m) + n));//输出数组C的值
}
}
}
int main()
{
int A[3][3] = { 1,2,3 , 4,5,6 , 7,8,9 };//初始化数组
int B[3][3] = { 9,8,7 , 6,5,4 , 3,2,1 };
int C[3][3];
int* pa = A;//分别定义三个指向三个数组首元素的指针
int* pb = B;
int* pc = C;
cheng(pa, pb, pc);//调用函数
return 0;
}
p291-1-指针-三个数从小到大输出-自己的思路
#include<stdio.h>
void swap(int** p1, int** p2)//要求原值不变指针改变,那传入的就应该是指针的指针。
{
int* p;
p = *p1;
*p1 = *p2;
*p2 = p;
}
//指针的指针相当于二阶导数f''(x),给它积回去就变成了原函数,原函数为输入的值的量,求导后为指针,二阶导数为指针的指针。
//即:f(x)<=>a f'(x)<=>pa<=>&a f''(x)<=>ppa<=>&pa ∫f'(x)<=>*ppa<=>pa<=>&a ∫∫f''(x)<=>**ppa<=>*pa <=>a
//通过互换指针的指向实现不改变值的量进行比较大小。
//c语言怎样更改指针的指向:https://ask.csdn.net/questions/1017258
//C语言二级指针(指向指针的指针)详解:http://c.biancheng.net/view/2016.html
//***p3等价于*(*(*p3))。*p3 得到的是 p2 的值,也即 p1 的地址;*(*p3) 得到的是 p1 的值,也即 a 的地址;经过三次“取值”操作后,*(*(*p3)) 得到的才是 a 的值。
int main()
{
int a, b, c;
int* pa, * pb, * pc;
int** ppa, ** ppb, ** ppc;
printf("输入三个数:");
scanf_s("%d %d %d", &a, &b, &c);
ppa = &pa;
ppb = &pb;
ppc = &pc;
pa = &a;
pb = &b;
pc = &c;
if (a > b)
{
swap(ppa, ppb);//如果想在函数内修改函数外的值,只能通过传入其指针或引用来修改
}
if (a > c)
{
swap(ppa, ppc);
}
if (b > c)
{
swap(ppb, ppc);
}
printf("该三个数从小到大为:%d %d %d\n", *pa, *pb, *pc);
printf("输入的三个数为:%d %d %d\n", a, b, c);
return 0;
}
p291-1-指针-三个数从小到大输出
#include<stdio.h>
void swap(int* p1, int* p2)//将指针的对象互换。。。。而不需要第三个指针,只需要一个中间变量p而不是*p。。。操
{
int p;
p = *p1;
*p1 = *p2;
*p2 = p;
}
//void swap(int* p1, int* p2)
//{
// int c;
// int* p=&c;//只要给函数中的局部指针变量一个任意地址,程序就能运行。
//
// *p = *p1;
// *p1 = *p2;
// *p2 = *p;
//}
int main()
{
int a, b, c;
int* pa, * pb, * pc;
//int* p;
printf("输入三个数:");
scanf_s("%d %d %d", &a, &b, &c);
pa = &a;
pb = &b;
pc = &c;
if (a > b)
{
swap(pa,pb);
/*p = pa;
pa = pb;
pb = p;*/
}
if (a > c)
{
swap(pa, pc);
/*p = pa;
pa = pc;
pc = p;*/
}
if (b > c)
{
swap(pb,pc);
/*p = pb;
pb = pc;
pc = p;*/
}
printf("该三个数从小到大为:%d %d %d", *pa,*pb,*pc);
printf("该三个数从小到大为:%d %d %d", a,b,c);
return 0;
}
p215-2-函数求根
#include<stdio.h>
#include<math.h>
float da(float a, float b, float c, float p)//应写上括号里的类型float 否则报错了。。。
{
float q;
float x1, x2;
q = sqrt(p);
x1 = (-b + q) / (2 * a);
x2 = (-b - q) / (2 * a);
printf("%5.2fx^2+%5.2fx+%5.2f=0的两个根为:x1=%f x2=%f", a, b, c, x1, x2);
}
float deng(float a,float b,float c)
{
float x;
x = -b / 2 * a;
printf("%5.2fx^2+%5.2fx+%5.2f=0的两个根为:x1=%f x2=%f", a, b, c, x, x);
}
float xiao(float a, float b, float c)
{
printf("%5.2fx^2+%5.2fx+%5.2f=0该方程无解", a, b, c);
}
int main()
{
float a, b, c;
float p;
printf("请输入abc的值:");
scanf_s("%f %f %f", &a, &b, &c);
p = b * b - 4 * a * c;
if (p > 0)
{
da(a, b, c, p);
}
if (p == 0)
{
deng(a, b, c);
}
if (p < 0)
{
xiao(a, b, c);
}
return 0;
}