一篇文章带你了解论C语言中算法的重要性

目录
  • 一、问题一(打印阶乘)
    • 问题描述:
    • 问题分析:
    • 解决方案:
      • 1.让我们检查一下结果,发现问题很有可能是循环的时候没有循环本身
      • 2.这里要引入C++中STL库的一个知识点
  • 二、问题二(比较多项式计算时间)
    • 问题描述:
    • 问题分析:
    • 解决方案:
  • 总结

一、问题一(打印阶乘)

问题描述:

打印出数字一到数字20的阶乘

一开始,我总会多打印出一个1,这令我十分苦恼,并且从n等于13开始,数据就开始溢出

问题分析:

让我们分析一下问题,这里面存在着两个问题:

1.多打印出一个1

2.数据溢出

解决方案:

1.让我们检查一下结果,发现问题很有可能是循环的时候没有循环本身

for (i = 1; i < num; i++)//这句话明显错了

改成

for (i = 1; i <= num; i++) {//i的值要乘以它本身!
			n = n * i;
		}

2.这里要引入C++中STL库的一个知识点

常规的32位整数只能够处理40亿以下的数。

如果遇到比40亿要大的数,就要用到C++的64位扩展。不同的编译器对64位整数的扩展有所不同。这个我也是听别人科普的,大家可以站内搜索一下。

优化后的代码如下:

#include <stdio.h>
void main() {
	__int64 fac(int num);
	int n = 1;
	int num;
	for (num = 0; num <= 20; ++num) {
		printf("%3d! = %I64d\n", num, fac(num));
	}
}
__int64 fac(int num) {
	register __int64 n = 1, i;     //寄存器变量
		for (i = 1; i <= num; i++) {//i的值要乘以它本身!
			n = n * i;
		}
		return n;
}

二、问题二(比较多项式计算时间)

问题描述:

这里先科普几个测试代码中的知识点:

这个表示本程序开始计时:

start = clock();

本程序结束计时:

stop = clock();

clock tick :时钟打点

CLK_TCK:机器时钟每秒所走的时钟打点数

问题分析:

首先这个问题有两种算法:

直接算

p1 += (pow(x, i)/i);

把x当成公因式提出计算(秦九韶法)

p2 = 1.0/(a[i - 1])+ (x*p2);

然后我发现了三个问题:

1.测量不出时间

2.程序重复性高

3.第一种结果和第二种结果不一致

解决方案:

1.让被测函数重复运行多次,使得测出的总时钟打点间隔充分长,最后计算被测函数除以运行次数即可得出平均每次的运行时间

duration = ((double)(stop - start)) / CLK_TCK / MAXK;

2.可以通过多设置几个函数,并调用函数解决问题

3.这是算法的问题

这个地方真的特别容易出错,我改了不知道多少遍。。。。。。

double f2(int n, double a[], double x) {
	int i;
	double p2 = 1.0/a[n];
	for (i = n; i > 0; i--) {
		p2 = 1.0/(a[i - 1])+ (x*p2);//算法思路出毛病了(数学)
	}
	return p2;
}

总体的代码:

#include <stdio.h>
#include <math.h>
#include <time.h>
clock_t start, stop;
double duration;
#define MAXN 101//数组里元素个数(多项式的系数),如果看n值需要减一,因为有a0
#define MAXK 1000//重复调用的次数
double f1(int n, double a[], double x)
{
	double p1 = a[0];//a[0]都已经算出来了,循环从1开始
	for (int i = 1; i <= n; i++) {
		p1 += (pow(x, i)/i);
	}
	return p1;
}
double f2(int n, double a[], double x) {
	int i;
	double p2 = 1.0/a[n];
	for (i = n; i > 0; i--) {
		p2 = 1.0/(a[i - 1])+ (x*p2);//算法思路出毛病了(数学)
	}
	return p2;
}
double ceshijian()
{
	stop = clock();//停止计时
	duration = ((double)(stop - start)) / CLK_TCK / MAXK;//计算单次运行时间
	printf("ticks=%f\n", (double)(stop - start));
	printf("duration=%6.2e\n", duration);
	return 0;
}
int main()
{
	int i;
	double a[MAXN];
	for (i = 0; i < MAXN; i++) {
		a[i] = (double)i;
	}//输入的早就是i值了
	a[0] = 1;
	//不在测试范围内的准备工作写在clock()调用之前
	start = clock();//开始计时
	for (int i = 0; i < MAXK; i++)//重复调用
		f1(MAXN - 1, a, 1.1);//被测函数,这里如果写数组的话就越界了,而且要调用某个值是不确定的,只能写a,因为要定义的就是a值
	printf("第一种结果为%f\n", f1(MAXN - 1, a, 1.1));
	ceshijian();

	start = clock();//开始计时
	for (i = 0; i < MAXK; i++)
		f2(MAXN - 1, a, 1.1);//被测函数,这里如果写数组的话就越界了,而且要调用某个值是不确定的
	printf("第二种结果为%f\n", f2(MAXN - 1, a, 1.1));
	ceshijian();
	return 0;
}

结果如下

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • C语言的进制转换及算法实现教程

    1.其他进制转十进制 1.1.二进制转十进制 转换规程: 从最低位开始,将每个位上的数提取出来,乘以2的(位数-1)次方,然后求和,例如: 二进制 1011 = 1*2^0 + 1*2^1 + 0*2^2 + 1*2^3 = 1 + 2 + 0 + 8 = 11 1.2.八制转十进制 转换规则: 从最低位开始,将每个位上的数提取出来,乘以8的(位数-1)次方,然后求和,例如: 八进制 0123 = 3*8^0 + 2*8^1 + 1*8^2 = 3+16+64 = 83 1.3.十六进制转十进制

  • C语言实现扫雷算法简易版

    扫雷分析 从小到大你或许没玩过但一定听过的游戏--扫雷 首先我们来分一下"扫雷"的功能 这是一个简单难度的扫雷,从外观上,我们可以发现可供用户操作的棋盘范围是9×9的范围,也就是我们建立的棋盘大小至少要为9,但是问题也就来了,我们如果只建立9×9的棋盘,那么在边缘的格子要进行提示操作的时候就会出现数据越界问题. 为了解决数据越界的问题,我们最好创建一个比可视界面大一圈的数组,即11×11的数组 但是在我们开始做这个小游戏的时候发现了一个问题--一个数组里面包含的数据太多了,可能会发生数

  • c语言实现的几种常用排序算法

    概述 最近重新回顾了一下数据结构和算法的一些基本知识,对几种排序算法有了更多的理解,也趁此机会通过博客做一个总结. 1.选择排序-简单选择排序 选择排序是最简单的一种基于O(n2)时间复杂度的排序算法,基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小(大)值. 算法实现: void selectSort(int arr[], int n) { int i, j , minValue, tmp; for(i = 0; i < n-1; i++) { minValue

  • C语言实现三子棋(井字棋)算法

    本文实例为大家分享了C语言实现三子棋算法,供大家参考,具体内容如下 游戏文件主干(test.c): #include"game.h" void menu()//游戏菜单 { printf("************************************************\n"); printf("********** 1.play *********\n"); printf("********** 0.exit ****

  • C语言朴素模式匹配算法实例代码

    一.什么是字符串的模式匹配? 字符串模式匹配:在主串中找到与模式串相同的子串,并返回其所在位置. 注意: ①.子串--主串的一部分,一定存在. ②.模式串--不一定能在主串中找到 二.朴素模式匹配算法 主串长度为n,模式串长度为m. 朴素模式匹配算法:将主串中所有长度为m的子串依次与模式串匹配对比,直到找到一个完全匹配的子串,或所有的子串都不匹配为止. 最多对比n-m+1个子串 (一)通过数组下标实现朴素模式匹配算法 若当前⼦串匹配失败,则主串指针 i 指向下⼀个⼦串的第⼀个位置,模式串指针 j

  • 一篇文章带你了解论C语言中算法的重要性

    目录 一.问题一(打印阶乘) 问题描述: 问题分析: 解决方案: 1.让我们检查一下结果,发现问题很有可能是循环的时候没有循环本身 2.这里要引入C++中STL库的一个知识点 二.问题二(比较多项式计算时间) 问题描述: 问题分析: 解决方案: 总结 一.问题一(打印阶乘) 问题描述: 打印出数字一到数字20的阶乘 一开始,我总会多打印出一个1,这令我十分苦恼,并且从n等于13开始,数据就开始溢出 问题分析: 让我们分析一下问题,这里面存在着两个问题: 1.多打印出一个1 2.数据溢出 解决方案

  • 一篇文章带你玩转go语言的接口

    目录 一.其他语言 二.go语言 三.go接口实现多态 四.空接口的使用(重点) 4.1定义 4.2空接口使用 4.3空接口几个要注意的坑(我刚学时的错误) 总结 一.其他语言 其他语言中所提供的接口概念:接口主要作为不同组件之间的契约存在.对契约的实现是强制的(侵入式接口),你必须声明你的确实现了该接口.为了实现一个接口,你需要从该接口继承. interface IFoo { void Bar(); } // Java文法 // ... class Foo implements IFoo {

  • 一篇文章带你顺利通过Python OpenCV入门阶段

    目录 1. OpenCV 初识与安装 2. OpenCV 模块简介 3. OpenCV 图像读取,显示,保存 4. 摄像头和视频读取,保存 5. OpenCV 常用数据结构和颜色空间 6. OpenCV 常用绘图函数 7. OpenCV 界面事件操作之鼠标与滑动条 8. 图像像素.通道分离与合并 9. 图像逻辑运算 10. 图像 ROI 与 mask 掩膜 11. 图像几何变换 12. 图像滤波 13. 图像固定阈值与自适应阈值 14. 图像膨胀腐蚀 15. 边缘检测 16. 霍夫变换 17.

  • 一篇文章带你使用Typescript封装一个Vue组件(简单易懂)

    一.搭建项目以及初始化配置 vue create ts_vue_btn 这里使用了vue CLI3自定义选择的服务,我选择了ts.stylus等工具.然后创建完项目之后,进入项目.使用快捷命令code .进入Vs code编辑器(如果没有code .,需要将编辑器的bin文件目录地址放到环境变量的path中).然后,我进入编辑器之后,进入设置工作区,随便设置一个参数,这里比如推荐设置字号,点下.这里是为了生成.vscode文件夹,里面有个json文件. 我们在开发项目的时候,项目文件夹内的文件很

  • 一篇文章带你搞定SpringBoot中的热部署devtools方法

    一.前期配置 创建项目时,需要加入 DevTools 依赖 二.测试使用 (1)建立 HelloController @RestController public class HelloController { @GetMapping("/hello") public String hello(){ return "hello devtools"; } } 对其进行修改:然后不用重新运行,重新构建即可:只加载变化的类 三.热部署的原理 Spring Boot 中热部

  • 一篇文章带你搞定SpringBoot不重启项目实现修改静态资源

    一.通过配置文件控制静态资源的热部署 在配置文件 application.properties 中添加: #表示从这个默认不触发重启的目录中除去static目录 spring.devtools.restart.exclude=classpath:/static/** 或者使用: #表示将static目录加入到修改资源会重启的目录中来 spring.devtools.restart.additional-paths=src/main/resource/static 此时对static 目录下的静态

  • 一篇文章带你解决 IDEA 每次新建项目 maven home directory 总是改变的问题

    Maven是基bai于项目对象模型,可以通du过一小段描述信息来管理zhi项目的构建,报告和文档的软件项dao目管理工具. 重装个系统,各种问题,idea 也出现各种问题 装了个新版的 idea 2020 2.x 版本的,不知道咋回事,其他都好使,就是创建 SpringBoot 项目时: 加载 pom.xml 总是出错,原因就是,新建立的项目 maven home directory 总是乱,没有安装 设置的默认方式 我试了,改当前项目的,不好使 该默认设置,不好使,网上的其他方法也试了,很奇怪

  • 一篇文章带你使用SpringBoot基于WebSocket的在线群聊实现

    一.添加依赖 加入前端需要用到的依赖: <dependency> <groupId>org.webjars</groupId> <artifactId>sockjs-client</artifactId> <version>1.1.2</version> </dependency> <dependency> <groupId>org.webjars</groupId> <

  • 一篇文章带你搞定 springsecurity基于数据库的认证(springsecurity整合mybatis)

    一.前期配置 1. 加入依赖 <dependency> <groupId>com.alibaba</groupId> <artifactId>druid-spring-boot-starter</artifactId> <version>1.1.10</version> </dependency> <dependency> <groupId>mysql</groupId> &

  • 一篇文章带你搞定Ubuntu中打开Pycharm总是卡顿崩溃

    由于 Ubuntu 中的汉字输入实在是太不友好了,所以装了个 搜狗输入法,好不容易把 搜狗输入法装好,本以为可以开开心心的搞代码了,然而... pycharm 一打开,就崩溃,关不掉,进程杀死还是不行,只能关机重启. 本以为 pycharm 出现了问题,又重装了两遍,还是不行. 最终发现竟然是搜狗输入法以及 fcitx 输入法的锅 唉,只能老老实实的把 fctix 和搜狗输入法卸载了: (1)Ubuntu 软件里卸载 fctix,然后将键盘输入法系统改成 IBus (2)卸载搜狗输入法 先查找软

随机推荐