图计算框架有哪些？九宫图算法的算法实现

本文目录

• 图计算框架有哪些
• 九宫图算法的算法实现
• 程序员必须掌握哪些算法
• 九宫图算法的实现步骤
• 镂空图算法的基本思想是什么
• 如何用粒度分析资料通过图算法以福克和沃德的公式求各粒度参数
• 农夫过河的图算法

图计算框架有哪些

图计算框架回顾 0 从数据并行到图并行 自从04 年 Google 公开了它的 MapReduce 之后,大家就像是发现了什么新大陆一样以极大的热情投入到新型计算框

九宫图算法的算法实现

// 九宫图算法；
//////////////////////////////////////
#include《sio.h》
#include《time.h》
#include《slib.h》
//////////////////////////////////
//// the function defination
//////////////////////////////////
void create(int );
void show(int );
void set_value(int );
void aim_get(int );
void target(int );
void judge_x1(int );
void judge_x2(int );
void judge_x3(int );
void judge_x4(int );
void judge_x5(int );
void shift_all(int );
void shift_low_six(int );
void anti_shift_all(int );
void shift_low_four(int );
void last_shift(int );
void set_x5(int );
///////////////////////////////////////
////// the main function body ////
////////////////////////////////////////
main()
{
srand(time(NULL));
int cDiagram;
create(cDiagram); /////// creat the new array ,set the value are 10;
set_value(cDiagram);
//last_shift(cDiagram);
return 0;
}
///////////////////////////////////////
/// 建立一个3*3数组，初值都设为10；//
//////////////////////////////////////
void create(int array)
{
printf(“\n\n***********************************\n\n“);
printf(“九宫图算法实现过程\n\n“);
printf(“***********************************\n\n“);
int line;
int row;
for(line=0;line《3;line )
{
for(row=0;row《3;row )
{
array[line][row]=10;
}
}
// set_value(array);
//show(array);
}
/////////////////////////////////////////
/// 显示数组状态 ////
////////////////////////////////////////
void show(int array)
{
for(int i=0;i《3;i )
{
for(int j=0;j《3;j )
{
printf(“=“,array[i][j]);
}
printf(“\n\n“);
}
}
///////////////////////////////
/// 产生数组的初始状态 ///////
///////////////////////////////
void set_value(int array)
{
int i=0;
int rand_num_line;
int rand_num_row;
printf(“ \n\n九宫图的初始值为：\n\n“);
while(i《=8)
{
rand_num_line=rand()%3;
rand_num_row=rand()%3;
if(array[rand_num_line][rand_num_row]!=i&& array[rand_num_line][rand_num_row]==10)
{
array[rand_num_line][rand_num_row]=i;
i;
}
}
show(array);
//printf(“ let’s begin!!\n“);
aim_get(array);
}
////////////////////////////////////////////////////////
//// judge the initial array get the target or no ! ///
//////////////////////////////////////////////////////////
void aim_get(int array)
{
int aim={{1,2,3},{8,0,4},{7,6,5}};
int line;
int row;
int judge=0;
for(line=0;line《3;line )
{
for(row=0;row《3;row )
{
if(array[line][row]!=aim[line][row])
{
judge=1;
}
}
}
if(judge==1)
{
judge_x1(array);
}
else
{
target(array);
}
}
/////////////////////////////////////
/////// the target diagram //////////
/////////////////////////////////////
void target(int array)
{
printf(“\n\n the last diagram is :\n“);
show(array);
}
////////////////////////////////////
///judge the x1 is 1 or no! ///////
////////////////////////////////////
void judge_x1(int array)
{
//int x1=1;
int temp;
//printf(“ \n\n\n the array=%d\n\n“,array);
if(array!=1 && array!=0) // x3!=1 || x3!=0;
{
while(array!=1)
{
//printf(“i am here!!1“);
temp=array;
array=array;
array=array;
array=array;
array=array;
array=array;
array=array;
array=array;
array=temp;
}
}
else
{
if(array==0) // x3==0;
{
// printf(“\n\n array=0\n\n“);
temp=array;
array=array;
array=temp;
judge_x1(array);
goto tt;
}
else /// x3==1;
{ //printf(“\n\narray should is 1, %d“,array);
if(array==0) //// x0==0;
{
temp=array;
array=array;
array=temp;
judge_x1(array);
}
else //// x3==1 && x0!=0;
{
shift_all(array);
judge_x1(array);
}
}
}
printf(“ 确定了X1位置后，九宫图为：\n“);

程序员必须掌握哪些算法

一.基本算法:

枚举. (poj1753,poj2965)

贪心(poj1328,poj2109,poj2586)

递归和分治法.

递推.

构造法.(poj3295)

模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.

最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)

二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)

排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

简单并查集的应用.

哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)

堆

trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)

型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学

组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.

几何公式.

叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:
一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)

较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)

最小费用最大流(poj2516,poj2516,poj2195)

双连通分量(poj2942)

强连通分支及其缩点.(poj2186)

图的割边和割点(poj3352)

最小割模型、网络流规约(poj3308)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

九宫图算法的实现步骤

第一步：菱形斜填写
第二步：菱形四角的3和7,1和9交换，如下图
第三步：9和1插队进去，如图

先将1—9九个数按如下图排列
1
4 b 2
7 c 5 a 3
8 d 6
9
然后将a用7代替，同理1换d，3换c，9换b
便可得如下排列：
4 9 2
3 5 7
8 1 6
此方法也可推导至所有的基数的平方宫图进行排列。
方法2：以中下格为起点，按右下为方向顺序填写（想象格子上下相连，左右相连），遇到右下格已占，填入正上方格内。
以25格为例： 11 18 25 2 9
10填左方 10↑
11填上方 12 19 21 3
4填左方 4 6 13 20↑ 11填上方 22
23填左方 23 5↑
6填上方 7 14 16
17填左方 17
18填上方 24
25填上方 1
2填上方 8
9填上方 15↑ 16填上方

镂空图算法的基本思想是什么

在开发界面及棋牌游戏过程中，需要很多镂空的图片,而且图片形式一般比较固定.

所以封装了几种常见的镂空方法.

1. 用于没有掩码图,只有指定透明色,不进行伸缩

void DrawTransBitmap( HDC hdcDest, // 目标DC
int nXOriginDest, // 目标X偏移
int nYOriginDest, // 目标Y偏移
int nWidthDest, // 目标宽度
int nHeightDest, // 目标高度
HDC hdcSrc, // 源DC
int nXOriginSrc, // 源X起点
int nYOriginSrc, // 源Y起点
COLORREF crTransparent // 透明色,COLORREF类型
);

适用图片:

2. 用于没有掩码图,只有指定透明色,可以进行伸缩

void DrawTransBitmap( HDC hdcDest, // 目标DC
int nXOriginDest, // 目标X偏移
int nYOriginDest, // 目标Y偏移
int nWidthDest, // 目标宽度
int nHeightDest, // 目标高度
HDC hdcSrc, // 源DC
int nXOriginSrc, // 源X起点
int nYOriginSrc, // 源Y起点
int nWidthSrc, // 源宽度
int nHeightSrc, // 源高度
COLORREF crTransparent // 透明色,COLORREF类型
);适用图片:同1,可拉伸

3.指定掩码图,和掩码图属于不同图片

void DrawTransBitmap( HDC hdcDest, // 目标DC
int nXOriginDest, // 目标X偏移
int nYOriginDest, // 目标Y偏移
int nWidthDest, // 目标宽度
int nHeightDest, // 目标高度
HDC hdcSrc, // 源DC
HDC hdcMask, //掩码DC
int nXOriginSrc, // 源X起点
int nYOriginSrc, // 源Y起点
COLORREF crTransparent // 透明色,COLORREF类型
);适用图片: 和

4.指定图片和掩码图同属于一张图片

void DrawTransBitmap(HDC hDC,
int nPosX,
int nPosY,
int nCX,
int nCY,
HBITMAP hObj
);适用图片:

5.得到位图HRGN

HRGN CreateBitmapRgn(int nWidth,int nHeight,HBITMAP hbmp,COLORREF cTrans);适用图片:

以下是完整代码

//用于没有掩码图,只有指定透明色,不进行伸缩
void CCommon::DrawTransBitmap( HDC hdcDest, // 目标DC
int nXOriginDest, // 目标X偏移
int nYOriginDest, // 目标Y偏移
int nWidthDest, // 目标宽度
int nHeightDest, // 目标高度
HDC hdcSrc, // 源DC
int nXOriginSrc, // 源X起点
int nYOriginSrc, // 源Y起点
COLORREF crTransparent // 透明色,COLORREF类型
)
......{
HBITMAP hOldImageBMP, hImageBMP = CreateCompatibleBitmap(hdcDest, nWidthDest, nHeightDest); // 创建兼容位图
HBITMAP hOldMaskBMP, hMaskBMP = CreateBitmap(nWidthDest, nHeightDest, 1, 1, NULL); // 创建单色掩码位图
HDC hImageDC = CreateCompatibleDC(hdcDest);//临时DC
HDC hMaskDC = CreateCompatibleDC(hdcDest);//临时掩码DC
hOldImageBMP = (HBITMAP)SelectObject(hImageDC, hImageBMP);
hOldMaskBMP = (HBITMAP)SelectObject(hMaskDC, hMaskBMP);

// 将源DC中的位图拷贝到临时DC中,源DC已经载入位图
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hdcSrc, nXOriginSrc, nYOriginSrc, SRCCOPY);

// 设置临时DC的透明色
SetBkColor(hImageDC, crTransparent);

// 生成透明区域为白色，其它区域为黑色的临时掩码DC的掩码位图
// 位图来自临时DC
BitBlt(hMaskDC, 0, 0, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCCOPY);

// 生成透明区域为黑色，其它区域保持不变的位图
SetBkColor(hImageDC, RGB(0,0,0));
SetTextColor(hImageDC, RGB(255,255,255));
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);

// 透明部分保持屏幕不变，其它部分变成黑色
SetBkColor(hdcDest,RGB(255,255,255));
SetTextColor(hdcDest,RGB(0,0,0));
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);

// “或“运算,生成最终效果
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCPAINT);

// 清理、恢复
SelectObject(hImageDC, hOldImageBMP);
DeleteDC(hImageDC);
SelectObject(hMaskDC, hOldMaskBMP);
DeleteDC(hMaskDC);
DeleteObject(hImageBMP);
DeleteObject(hMaskBMP);
}

//用于没有掩码图,只有指定透明色，可以进行伸缩
void CCommon::DrawTransBitmap( HDC hdcDest, // 目标DC
int nXOriginDest, // 目标X偏移
int nYOriginDest, // 目标Y偏移
int nWidthDest, // 目标宽度
int nHeightDest, // 目标高度
HDC hdcSrc, // 源DC
int nXOriginSrc, // 源X起点
int nYOriginSrc, // 源Y起点
int nWidthSrc, // 源宽度
int nHeightSrc, // 源高度
COLORREF crTransparent // 透明色,COLORREF类型
)
......{
HBITMAP hOldImageBMP, hImageBMP = CreateCompatibleBitmap(hdcDest, nWidthDest, nHeightDest); // 创建兼容位图
HBITMAP hOldMaskBMP, hMaskBMP = CreateBitmap(nWidthDest, nHeightDest, 1, 1, NULL); // 创建单色掩码位图
HDC hImageDC = CreateCompatibleDC(hdcDest);
HDC hMaskDC = CreateCompatibleDC(hdcDest);
hOldImageBMP = (HBITMAP)SelectObject(hImageDC, hImageBMP);
hOldMaskBMP = (HBITMAP)SelectObject(hMaskDC, hMaskBMP);

// 将源DC中的位图拷贝到临时DC中
if (nWidthDest == nWidthSrc && nHeightDest == nHeightSrc)
......{
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hdcSrc, nXOriginSrc, nYOriginSrc, SRCCOPY);
}
else
......{
StretchBlt(hImageDC, 0, 0, nWidthDest, nHeightDest,
hdcSrc, nXOriginSrc, nYOriginSrc, nWidthSrc, nHeightSrc, SRCCOPY);
}

// 设置透明色
SetBkColor(hImageDC, crTransparent);

// 生成透明区域为白色，其它区域为黑色的掩码位图
BitBlt(hMaskDC, 0, 0, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCCOPY);

// 生成透明区域为黑色，其它区域保持不变的位图
SetBkColor(hImageDC, RGB(0,0,0));
SetTextColor(hImageDC, RGB(255,255,255));
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);

// 透明部分保持屏幕不变，其它部分变成黑色
SetBkColor(hdcDest,RGB(0xff,0xff,0xff));
SetTextColor(hdcDest,RGB(0,0,0));
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hMaskDC, 0, 0, SRCAND);

// “或“运算,生成最终效果
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCPAINT);

SelectObject(hImageDC, hOldImageBMP);
DeleteDC(hImageDC);
SelectObject(hMaskDC, hOldMaskBMP);
DeleteDC(hMaskDC);
DeleteObject(hImageBMP);
DeleteObject(hMaskBMP);

}

指定掩码图,和掩码图属于不同图片
void CCommon::DrawTransBitmap( HDC hdcDest, // 目标DC
int nXOriginDest, // 目标X偏移
int nYOriginDest, // 目标Y偏移
int nWidthDest, // 目标宽度
int nHeightDest, // 目标高度
HDC hdcSrc, // 源DC
HDC hdcMask,
int nXOriginSrc, // 源X起点
int nYOriginSrc, // 源Y起点
COLORREF crTransparent // 透明色,COLORREF类型
)
......{

HBITMAP hOldImageBMP, hImageBMP = CreateCompatibleBitmap(hdcDest, nWidthDest, nHeightDest); // 创建兼容位图
HDC hImageDC = CreateCompatibleDC(hdcDest);//临时DC
hOldImageBMP = (HBITMAP)SelectObject(hImageDC, hImageBMP);

// 将源DC中的位图拷贝到临时DC中,源DC已经载入位图
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hdcSrc, nXOriginSrc, nYOriginSrc, SRCCOPY);
// 设置临时DC的透明色
SetBkColor(hImageDC, crTransparent);
// 生成透明区域为黑色，其它区域保持不变的位图
SetBkColor(hImageDC, RGB(0,0,0));
SetTextColor(hImageDC, RGB(255,255,255));
BitBlt(hImageDC, 0, 0, nWidthDest, nHeightDest, hdcMask, 0, 0, SRCAND);
// 透明部分保持屏幕不变，其它部分变成黑色
SetBkColor(hdcDest,RGB(255,255,255));
SetTextColor(hdcDest,RGB(0,0,0));
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hdcMask, 0, 0, SRCAND);
// “或“运算,生成最终效果
BitBlt(hdcDest, nXOriginDest, nYOriginDest, nWidthDest, nHeightDest, hImageDC, 0, 0, SRCPAINT);
// 清理、恢复
SelectObject(hImageDC, hOldImageBMP);
DeleteDC(hImageDC);
DeleteObject(hImageBMP);
}

指定图片和掩码图同属于一张图片
void CCommon::DrawTransBitmap(HDC hDC, int nPosX, int nPosY, int nCX, int nCY, HBITMAP hObj)
......{
HDC hMemDC= CreateCompatibleDC(hDC);
HBITMAP hOldBMP=(HBITMAP)::SelectObject(hMemDC,hObj);
BitBlt(hDC,nPosX,nPosY,nCX,nCY, hMemDC,nCX,0,SRCAND);
BitBlt(hDC,nPosX,nPosY,nCX,nCY, hMemDC,0,0,SRCPAINT);
SelectObject(hMemDC,hOldBMP);
DeleteDC(hMemDC);

}

HRGN CCommon::CreateBitmapRgn(int nWidth,int nHeight,HBITMAP hbmp, COLORREF TransColor)
......{

HDC hmemDC;
//创建与传入DC兼容的临时DC
hmemDC = ::CreateCompatibleDC(NULL);

HBITMAP hOldBmp = (HBITMAP)::SelectObject(hmemDC,hbmp);

//创建总的窗体区域，初始region为0
HRGN hrgn;
hrgn = ::CreateRectRgn(0,0,0,0);

int y;
for(y=0;y《nHeight ;y++)
......{
HRGN rgnTemp; //保存临时region

int iX = 0;
do
......{
//跳过透明色找到下一个非透明色的点.
while (iX 《 nWidth && ::GetPixel(hmemDC,iX, y) == TransColor)
iX++;

//记住这个起始点
int iLeftX = iX;

//寻找下个透明色的点
while (iX 《 nWidth && ::GetPixel(hmemDC,iX, y) != TransColor)
++iX;

//创建一个包含起点与重点间高为1像素的临时“region”
rgnTemp=::CreateRectRgn(iLeftX, y, iX, y+1);

//合并到主“region“.
CombineRgn( hrgn,hrgn,rgnTemp, RGN_OR);

//删除临时“region“,否则下次创建时和出错
::DeleteObject(rgnTemp);
}while(iX 《nWidth );
iX = 0;
}

::SelectObject(hmemDC,hOldBmp);
::DeleteDC(hmemDC);

return hrgn;

}

如何用粒度分析资料通过图算法以福克和沃德的公式求各粒度参数

9. 图算法我不知道是啥，可以从软件直接输出含量为5%,25%等等的值，再用公式Φ=-log2 d，把输出的um转换成Φ，在套入各个参数公式就行了。
10C-M图是应用每个样品的C值和M 值绘成的图形。C是粒度分析资料累积曲线上颗粒含量1%处对应的粒径，M值是累积曲线上 50 % 处对应的粒径，即粒度中值。C值与样品中最粗颗粒的粒径相当，代表了水动力搅动开始搬运的最大能量; M值是中值，代表了水动力的平均能量。
对于每一个样品都可以用其C值和M值，在以C值（um)为纵坐标、以 M 值(um)为横坐标的双对数坐标纸（当CM单位为ф时则用线性坐标就行）上投得一个点。

C-M图是帕塞加 (Passega，1957，1964) 提出的。帕塞加将搬运沉积物的底流分为以下两种形式：
牵引流：河流、海(湖) 流、触及海 (湖) 底的波浪都属于牵引流，它以滚动或悬浮两种方式搬运沉积物。在悬浮搬运中还包括递变悬浮、均匀悬浮和远洋悬浮。
浊流：这是一种流速很快的高密度流，它主要以悬浮方式搬运沉积物。由于有大量泥、砂，甚至卵石悬浮其中，故水流十分混浊。
浊流沉积与牵引流沉积在C-M 图上有较明显的区别。在C-M图中，将C，M 点连成一条线，构成C=M基线。浊流沉积的图形以平行于C=M基线为特征;而牵引流沉积的图形则只有较短的一部分平行C=M基线，或者完全不与 C = M 基线平行。
(1) 牵引流沉积的 C-M 图
在 C-M 图中，牵引流沉积的典型图形可划分为 N—O—P-Q—R—S 各段，1 表示牵引流沉积，2 表示浊流沉积，3 表示静水悬浮沉积。Ⅰ，Ⅱ，Ⅲ，Ⅸ段表示 C 》 1000μm，Ⅳ，Ⅴ，Ⅵ，Ⅶ，Ⅷ段表示 C 《 1000μm 。

帕塞加（Passega）牵引流沉积C-M模式图

1) QR 段代表递变悬浮沉积。递变悬浮搬运是指在流体中悬浮物质由下向上粒度逐渐变细，密度逐渐变低。它一般位于水流底部，常是由于涡流发育造成的。当涡流流速降低时，迅速发生滚动。递变悬浮沉积物的一个最大特点是C与M成比例地增加，即C值与M值相应变化，从而使这段图形与C=M基线平行。
在牵引流沉积中，C值常指示最大的地质营力。QR段C的最大值以Cs表示，一般认为Cs是代表底部的最大搅动指数。而这段的最小值Cu则代表底部的最小搅动指数。
2) RS 段为均匀悬浮，是粒径和密度不随深度变化的完全悬浮。均匀悬浮常是递变悬浮之上的上层水流搬运方式。在弱水流中可能不存在递变悬浮，而是由均匀悬浮直接与底床接触。均匀悬浮的物质主要为粉砂和泥质的混合物，最粗粒度为细砂。由于均匀悬浮搬运常不受底流分选，在河流中从上游至下游沉积物的粒度成分变化不大，只是粗粒级含量相对减少。因此在RS段中C值往往基本不变，而M值向S 端减小。RS段的最大C值即Cu，它代表均匀悬浮搬运的最大粒级。
3) PQ段仍以悬浮搬运为主，但含有少量滚动搬运组分。由上游至下游C值变化而 M值不变，说明随着地质营力的减弱，越向下游滚动组分的颗粒越小。但由于滚动颗粒的数量并不多，因此 M 值基本不变。PQ 段 P 点附近的 C 值以 Cr 表示，它代表着最易作滚动搬运的颗粒直径。
4) OP 段以滚动搬运为主，滚动组分与悬浮组分相混合。C值一般大于 800μm，但由于滚动组分中有悬浮物质的参加，从而使 M 值有明显的变化。
5) NO 段基本上由滚动颗粒组成，C值一般大于1mm(1000μm)，常构成河流的砂坝砾石堆积物。
具体到某一地层成因单位来看，其 C-M 图常常不是包含上述所有的段，而是只有少数几个段，各段的位置和大小亦不尽相同。如能抓住这些特点并结合沉积构造序列分析，将其与典型的 C-M 图形进行对比，便可作出沉积成因解释。除河流沉积外，还有一些其他类型的牵引流沉积。
在海滩地带，由于环境动荡，细的悬浮物质不沉降，因此粗颗粒不能被埋藏，滚动颗粒可以搬运很长距离后再沉积，所以在海滩沉积物中滚动组分很多。海滩沉积物的C-M图表现为分散的图形，一般C》200μm，M》100μm，样品点在Ⅰ，Ⅱ，Ⅲ，Ⅳ区中散布。远洋区集中了最细的悬浮沉积物，其颗粒均十分细小，在C-M图上构成了3区。除深海外，深湖、泻湖、海湾、礁湖等静水盆地沉积也属于这一类型。
(2) 浊流沉积的 C-M 图是很好的平行于C=M基线的图形。浊流的流速很快，当流速降低时，悬浮物质移向底部，使底部密度不断增加，最终形成整体的沉降作用，并形成未分选的沉积物。浊流沉积所特有的递变层理，正是递变悬浮和整体沉降作用的反映。
浊流为高密度流，沉积作用进行很快，颗粒沉积后随即被埋藏，因而组分中缺乏滚动颗粒。其结果是，在 C-M 图上浊流沉积物的 C 值与M 值密切相关变化，形成与 C =M 基线平行的图形。这一特点与牵引的递变悬浮沉积 (Q R段)相似。但 C值与M 值的变化幅度均较大，这一点却是浊流沉积 C-M 图的独有特征。如在浊流沉积 C-M图点群中画一条平均线，平均线与C=M基线的水平距离 Im能代表浊流沉积的分选性。Im值越小，说明沉积物的分选性越好。因为，在一般情况下 C 值与 M 值靠近是分选好的标志。这一道理在牵引流递变悬浮沉积物的分选性分析中亦适用。
由于沉积物点群在 C-M 图上的位置取决于沉积物的搬运沉积方式，因此利用 C-M图可对碎屑物质的搬运沉积条件作出判断。另外，各沉积环境都有其特征的 C-M 图模式，所以用 C-M 图也能为沉积环境解释提供参考依据。

农夫过河的图算法

#include《iostream》

using namespace std;

#define VertexNum 16 //最大顶点数

typedef struct // 图的顶点
{
int farmer; // 农夫
int wolf; // 狼
int sheep; // 羊
int veget; // 白菜
}Vertex;

typedef struct
{
int vertexNum; // 图的当前顶点数
Vertex vertex[VertexNum]; // 顶点向量（代表顶点）
bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关
}AdjGraph; // 定义图的邻接矩阵存储结构

bool visited[VertexNum] = {false}; // 对已访问的顶点进行标记（图的遍历）
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路径，即与某顶点到下一顶点的路径

// 查找顶点（F，W，S，V）在顶点向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 从0开始查找
for (int i = 0; i 《 graph-》vertexNum; i++)
{
if ( graph-》vertex[i].farmer == farmer && graph-》vertex[i].wolf == wolf
&& graph-》vertex[i].sheep == sheep && graph-》vertex[i].veget == veget )
{
return i; //返回当前位置
}
}

return -1; //没有找到此顶点
}

// 判断目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true; // 安全返回true
}
}

// 判断状态i与状态j之间是否可转换
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;

if (graph-》vertex[i].wolf != graph-》vertex[j].wolf)
{
k++;
}

if (graph-》vertex[i].sheep != graph-》vertex[j].sheep)
{
k++;
}

if (graph-》vertex[i].veget != graph-》vertex[j].veget)
{
k++;
}

// 以上三个条件不同时满足两个且农夫状态改变时，返回真, 也即农夫每次只能带一件东西过桥
if (graph-》vertex[i].farmer != graph-》vertex[j].farmer && k 《= 1)
{
return true;
}
else
{
return false;
}
}

// 创建连接图
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;

// 生成所有安全的图的顶点
for (int farmer = 0; farmer 《= 1; farmer++)
{
for (int wolf = 0; wolf 《= 1; wolf++)
{
for (int sheep = 0; sheep 《= 1; sheep++)
{
for (int veget = 0; veget 《= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph-》vertex[i].farmer = farmer;
graph-》vertex[i].wolf = wolf;
graph-》vertex[i].sheep = sheep;
graph-》vertex[i].veget = veget;
i++;
}
}
}
}
}

// 邻接矩阵初始化即建立邻接矩阵
graph-》vertexNum = i;
for (i = 0; i 《 graph-》vertexNum; i++)
{
for (j = 0; j 《 graph-》vertexNum; j++)
{
// 状态i与状态j之间可转化，初始化为1，否则为0
if (isConnect(graph, i, j))
{
graph-》Edge[i][j] = graph-》Edge[j][i] = true;
}
else
{
graph-》Edge[i][j] = graph-》Edge[j][i] = false;
}
}
}

return;
}

// 判断在河的那一边
char* judgement(int state)
{
return ( (0 == state) ? “左岸“ : “右岸“ );
}

// 输出从u到v的简单路径，即顶点序列中不重复出现的路径
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;

cout 《《 “farmer“ 《《 “, wolf“ 《《 “, sheep“ 《《 “, veget“ 《《 endl;

while (i != end)
{
cout 《《 “(“ 《《 judgement(graph-》vertex[i].farmer) 《《 “, “ 《《 judgement(graph-》vertex[i].wolf)
《《 “, “ 《《 judgement(graph-》vertex[i].sheep) 《《 “, “ 《《 judgement(graph-》vertex[i].veget) 《《 “)“;
cout 《《 endl;

i = retPath[i];
}

cout 《《 “(“ 《《 judgement(graph-》vertex[i].farmer) 《《 “, “ 《《 judgement(graph-》vertex[i].wolf)
《《 “, “ 《《 judgement(graph-》vertex[i].sheep) 《《 “, “ 《《 judgement(graph-》vertex[i].veget) 《《 “)“;
cout 《《 endl;
}

// 深度优先搜索从u到v的简单路径 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //标记已访问过的顶点

if (start == end)
{
return ;
}

for (i = 0; i 《 graph-》vertexNum; i++)
{
if (graph-》Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}

int main()
{
AdjGraph graph;
CreateG(&graph);

int start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);

if (visited[end]) // 有结果
{
printPath(&graph, start, end);
return 0;
}

return -1;
}