C语言算法有哪些 并举例和分析

一、C语言算法有哪些 并举例和分析

function gcd(a,b:integer):integer;

function lcm(a,b:integer):integer;

while lcm mod b>0 do inc(lcm,a);

A.小范围内判断一个数是否为质数：

function prime(n: integer): Boolean;

B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：

function prime(x:longint):integer;

else if x mod pr[i]=0 then exit;

lowcost,closest:array[1..maxn] of integer;

{寻找离生成树最近的未加入顶点k}

if(lowcost[j]<min) and(lowcost[j]<>0) then begin

lowcost[k]:=0;{将顶点k加入生成树}

{生成树中增加一条新的边k到closest[k]}

{修正各点的lowcost和closest值}

if cost[k,j]<lwocost[j] then begin

按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。

function find(v:integer):integer;{返回顶点v所在的集合}

while(i<=n) and(not v in vset[i]) do inc(i);

if i<=n then find:=i else find:=0;

for i:=1 to n do vset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}

p:=n-1; q:=1; tot:=0;{p为尚待加入的边数，q为边集指针}

{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}

i:=find(e[q].v1);j:=find(e[q].v2);

vset[i]:=vset[i]+vset[j];vset[j]:=[];

a:array[1..maxn,1..maxn] of integer;

b:array[1..maxn] of integer;{b[i]指顶点i到源点的最短路径}

mark:array[1..maxn] of boolean;

fillchar(mark,sizeof(mark),false);

mark[1]:=true; b[1]:=0;{1为源点}

If mark[i] then{对每一个已计算出最短路径的点}

if(not mark[j]) and(a[i,j]>0) then

if(best=0) or(b[i]+a[i,j]<best) then begin

b[best_j]:=best；mark[best_j]:=true;

B.Floyed算法求解所有顶点对之间的最短路径：

if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0;{p[I,j]表示I到j的最短路径上j的前驱结点}

for k:=1 to n do{枚举中间结点}

if a[i,k]+a[j,k]<a[i,j] then begin

a:array[1..maxn,1..maxn] of integer;

b,pre:array[1..maxn] of integer;{pre[i]指最短路径上I的前驱结点}

mark:array[1..maxn] of boolean;

procedure dijkstra(v0:integer);

fillchar(mark,sizeof(mark),false);

if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;

repeat{每循环一次加入一个离1集合最近的结点并调整其他结点的参数}

min:=maxint; u:=0;{u记录离1集合最近的结点}

if(not mark[i]) and(d[i]<min) then begin

if(not mark[i]) and(a[u,i]+d[u]<d[i]) then begin

T:array[1..maxn,1..maxn] of boolean;

For j:=1 to n do T[I,j]:=t[I,j] or(t[I,k] and t[k,j]);

procedure dfs( now,color: integer);

if a[now,i] and c[i]=0 then begin{对结点I染色}

几个定义：顶点1为源点，n为汇点。

a.顶点事件最早发生时间Ve[j], Ve [j]= max{ Ve [j]+ w[I,j]},其中Ve(1)= 0;

b.顶点事件最晚发生时间 Vl[j], Vl [j]= min{ Vl[j]– w[I,j]},其中 Vl(n)= Ve(n);

c.边活动最早开始时间 Ee[I],若边I由<j,k>表示，则Ee[I]= Ve[j];

d.边活动最晚开始时间 El[I],若边I由<j,k>表示，则El[I]= Vl[k]– w[j,k];

若 Ee[j]= El[j]，则活动j为关键活动，由关键活动组成的路径为关键路径。

a.从源点起topsort,判断是否有回路并计算Ve;

找入度为0的点，删去与其相连的所有边，不断重复这一过程。

例寻找一数列，其中任意连续p项之和为正，任意q项之和为负，若不存在则输出NO.

定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点）

定义：经过图的每个顶点仅一次的回路。

充要条件：图连通且奇点个数为0个或2个。

9．判断图中是否有负权回路 Bellman-ford算法

x[I],y[I],t[I]分别表示第I条边的起点，终点和权。共n个结点和m条边。

for I:=0 to n-1 do d[I]:=+infinitive;

for j:=1 to m do{枚举每一条边}

if d[x[j]]+t[j]<d[y[j]] then d[y[j]]:=d[x[j]]+t[j];

if d[x[j]]+t[j]<d[y[j]] then return false else return true;

*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。

*同理，第n最短路径可在求解第n-1最短路径的基础上求解。

*部分背包问题可有贪心法求解：计算Pi/Wi

1．0-1背包：每个背包只能使用一次或有限次(可转化为一次)：

有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积(正整数)。要求从 n个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。

procedure search(k,v:integer);{搜索第k个物品，剩余空间为v}

if v-(s[n]-s[k-1])>=best then exit;{s[n]为前n个物品的重量和}

if v>w[k] then search(k+1,v-w[k]);

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。

实现:将最优化问题转化为判定性问题

f [I, j]= f [ i-1, j-w[i] ](w[I]<=j<=v)边界：f[0,0]:=true.

For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];

优化：当前状态只与前一阶段状态有关，可降至一维。

If f[j-w[I]] then f1[j]:=true;

F[I,j]为容量为I时取前j个背包所能获得的最大价值。

F [i,j]= max{ f [ i– w [ j ], j-1]+ p [ j ], f[ i,j-1]}

if j+now<=n then inc(c[j+now],a[j]);

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。

f[I,j]= f [ I-1, j– w[I]*k ](k=1.. j div w[I])

进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。

f[i,j]= max{ f [i- k*w[j], j-1]+ k*p[j]}(0<=k<= i div w[j])

其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。

If i-problem[j].time>=0 Then

t:=problem[j].point+f[i-problem[j].time];

求自然数n本质不同的质数和的表达式的数目。

思路一，生成每个质数的系数的排列，在一一测试，这是通法。

cal;{此过程计算当前系数的计算结果，now为结果}

if dep=l+1 then begin{生成所有系数}

for i:=0 to n div pr[dep] do begin

procedure try(dep,rest:integer);

if(rest<=0) or(dep=l+1) then begin

for i:=0 to rest div pr[dep] do

V个物品，背包容量为n，求放法总数。

if j+now*k<=n then inc(c[j+now*k],a[j]);

read(now);{读入第一个物品的重量}

i:=0;{a[i]为背包容量为i时的放法总数}

a[i]:=1; inc(i,now); end;{定义第一个物品重的整数倍的重量a值为1，作为初值}

i:=l;j:=r; mid:=a[(l+r) div 2];{将当前序列在中间位置的数定义为中间数}

while a[i]<mid do inc(i);{在左半部分寻找比中间数大的数}

while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数}

if i<=j then begin{若找到一组与排序目标不一致的数对则交换它们}

if l<j then qsort(l,j);{若未到两个数的边界，则递归搜索左右区间}

思路：当前a[1]..a[i-1]已排好序了，现要插入a[i]使a[1]..a[i]有序。

if a[i]>a[j] then swap(a[i],a[j]);

if a[j]<a[j-1] then swap( a[j],a[j-1]);{每次比较相邻元素的关系}

procedure sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数}

a[0]:=a[i]; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1}

if(k<m) and(a[k]<a[k+1]) then inc(k);{找出a[k]与a[k+1]中较大值}

if a[0]<a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end

a[i]:=a[0];{将根放在合适的位置}

for j:=n div 2 downto 1 do sift(j,n);

二、C语言的基本数据类型和举例!

1、C语言有五种基本数据类型：字符、整型、单精度实型、双精度实型和空类型。尽管这几种类型数据的长度和范围随处理器的类型和C语言编译程序的实现而异，但以bit为例，整数与CPU字长相等，一个字符通常为一个字节，浮点值的确切格式则根据实现而定

2、C语言还提供了几种聚合类型（aggregate

3、types），包括数组、指针、结构、共用体（联合）、位域和枚举

4、d类型外，基本类型的前面可以有各种修饰符。修饰符用来改变基本类型的意义，以便更准确地适应各种情况的需求。修饰符如下：

三、c语言define用法举例

在C语言中，`#define`是一个预处理指令，用于创建宏（macros）。宏是一种用于简化代码的工具，通常用于在编译时替换为一段代码或表达式。以下是一些`#define`用法和例子的说明：

1.**常量定义**：这是最常见的使用场景。你可以使用`#define`来定义一个常量，比如：

```c#define PI 3.14159 ```这将创建一个名为`PI`的宏，其值为3.14159。你可以在代码中使用这个宏来代替这个值，例如： ```c double radius= 5; double area= PI* radius* radius;//使用宏代替PI的值 ```

2.**宏函数**：你也可以使用`#define`来定义宏函数，它们在功能上类似于C语言中的函数。例如：

```c#define SQUARE(x)((x)*(x)) ```这将会创建一个宏函数`SQUARE`，它接受一个参数并返回这个参数的平方。你可以像调用函数一样使用这个宏： ```c double side= 3; double area= SQUARE(side);//使用宏函数SQUARE来计算面积 ```

3.**宏替换**：在编译时，预处理器会替换所有的宏定义。这意味着你可以使用宏来创建复杂的表达式，并在编译时进行简化或替换。例如：

```c#define ADD(x, y)((x)+(y)) ```这将会创建一个宏`ADD`，它接受两个参数并返回它们的和。你可以像这样使用它： ```c int a= 5; int b= 3; int sum= ADD(a, b);//在编译时，ADD宏将被替换为(5+ 3)，因此sum的值为8) ```总的来说，C语言的`#define`是一个强大的工具，可以帮助你简化代码、创建常量、定义函数等。然而，由于宏会在编译时被直接替换，使用不当可能会导致一些问题，比如名称冲突、不可预见的副作用等。因此，在使用宏时，最好仔细考虑它的含义和可能的后果。同时，为了避免错误和难以预期的行为，建议只使用没有副作用的简单宏。

除了上述常见用法外，你还可以使用`#include`预处理指令将头文件包含到代码中，同时使用`#define`在这些头文件中定义宏。这样可以使代码更易于管理和维护。

总的来说，C语言的`#define`是一个强大的工具，可以帮助你简化代码、创建常量、定义函数等。在使用它时，请务必小心并仔细考虑其可能的后果。