入位算法设计
1. 弄清楚题目的意思，列出题目的输入、输出、约束条件
其中又一道题目是这样的：“有一个mxn的矩阵，每一行从左到右是升序的，每一列从上到下是升序的。请实现一个函数，在矩阵中查找元素elem，找到则返回elem的位置。”题设只说了行和列是升序的，我在草稿纸上画了一个3x4的矩阵，里面的元素是1~12，于是我就想当然的认为矩阵的左上角是最小的元素，右下角是最大的元素。于是整个题目的思考方向就错了。
2. 思考怎样让算法的时间复杂度尽可能的小
继续以上面的题目为例子。可以有如下几种算法：
a. 遍历整个矩阵进行查找，那么复杂度为O(m*n)；
b. 因为每一行是有序的，所以可以对每一行进行二分查找，复杂度为O(m*logn)。但是这样只用到了行有序的性质。
c. 网上查了一下，最优的算法是从矩阵的左下角开始，比较左下角的元素（假设为X）与elem的大小，如果elem比X大，那么X所在的那一列元素就都被排除了，因为X是该列中最大的了，比X还大，那么肯定比X上面的都大；如果elem比X小，那么X所在的那一行就可以排除了，因为X是这一行里最小的了，比X还小那么肯定比X右边的都小。每迭代一次，矩阵的尺寸就缩小一行或一列。复杂度为O(max(m,n))。
可以先从复杂度较高的实现方法入手，然后再考虑如何利用题目的特定条件来降低复杂度。
3. 编写伪代码或代码
2. 2.设计算法:将一个元素插入到有序的顺序表中,使顺序表仍有序,并编写主函数测试算
#include<stdio.h>
#defineMAX5//预定义数组容量
intInsNum(int*a,intlen,intins)
{
inti=0,j;
while(ins>a[i]&&i<len)//找合适的位置插入ins
宏扰i++;
if(i==len)//到了数组末尾
a[i]=ins;
else//数组中间i处
{
for(j=len;j>i;j--)//从i起所有数乱凳据往后移一位
a[j]=a[j-1];
a[i]=ins;//插入位置i处
}
哗绝旅returnlen+1;
}
intmain()
{
inti,j,n,m;
inta[MAX]={2,5,11,15,17};//注意定义长度一定要比实际长度大
scanf("%d",&n);//输入要插入的数字
m=InsNum(a,5,n);//插入数组中
for(i=0;i<m;i++)//输出结果
{
printf("%d",a[i]);
}
return0;
}
3. 算法设计：输入N个只含一位数字的整数,试用基数排序的方法,对这N个数排序.
typedef struct
{
int key;
int next;
}SLRecType;
SLRecType R[N+1];
typedef struct
{
int f,e;
}SLQueue;
SLQueue B[10];
int Radixsort(SLRecType R[],int n)//设关键森铅字已输入到R数组
{
int k,t;
for(i=1;i<n;i++)R[i].next=i+1;
R[n].next=-1;p=1; //-1表示静态链表的结束
for(i=0;i<=9;i++){B[i].f=-1;b[i].e=-1} //设置队头队衫余尾指针初值
while(p!=-1) //一趟分配
{
k=R[p].key; //取关键字
if (B[k].f==-1)B[k].f=p; //修改队头指针
else R[B[k].e].next=p;
B[k].e=p;
p=R[p].next; /此塌好/一趟收集
}
i=0;
while(B[i].f==-1)i++;
t=B[i].e;p=B[i].f;
while(i<9)
{
i++;
if( B[i].f!=-1)
{
R[t].next=B[i].f;
t= B[i].e;
}
}
R[].next=-1;
return p; //返回第一个记录指针
}
4. 设计算法输入一个5位的整数n，输出n的各位数字的和(如n=13546，由于1+3+5+4+6=1
int n,s,temp;
n=12345；链散
temp=10000;
s=0;
for(int i=0;i<5;i++){
s+=n/temp;
n=n%temp;
temp=temp/迹唤雹姿帆10;
}
System.out.println(s);
5. 算法设计原则是什么
原则：首先说设计的算法必须是"正确的"，其次应有很好的"可读性"，还必须具有"健壮性"，最后应考虑所设计的算法具有"高效率与低存储量"。
所谓算法是正确的，除了应该满足算法说明中写明的"功能"之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。
在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。算法的效率指的是算法的执行时间，算法的存储量指的是算法执行过程中所需最大存储空间。
算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要讨论相应的算法。这里有两重意思，即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。
确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。
可行性指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题，例如，"求x和y的公因子"就不够基本。
输入值即为算法的操作对象，但操作的对象也可以由算法自身生成，如"求100以内的素数"，操作对象是自然数列，可以由变量逐个增1生成。
算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。
6. 算法设计-帮帮忙
这个估计要用文件输入
否则太累了
--我们必须尽量优化程序才能达到题目的要求。显然n实在是太大了，所以我们不但不可能忍受O(n2)的复杂度，甚至连n前面的系数过大都会造成超时。为了尽量减小时间复杂度，我们只能依靠自动机的理论。
自动机理论
一个DFA（确定性有限自动机）是一个五元组<∑, U, s, T, φ>，其中∑是字符集U 是一个有限的状态集合, s 是 U 的一个元素表示初始状态, T 是 U的一个子集，表示终止状态and φ : U × ∑ → U 是转移函数。
开始时自动机在初始状态s，每步它读入一个字符c，然后根据state=φ(state,c)进行状态的转移。如果当字符串结束时它达到了终止状态，那么就说它接受了字符串。
NFA（非确定性自动机）与DFA的主要区别就是，NFA从一个状态按照一个字符转移到的状态可能有多个。因此NFA需要使用一个状态集合来表示当前可能处在的状态。
把自动机用图来表示的话，一般用结点表示状态，而结点之间有标有某个字符的有向边，表示可以从边的起点通过这个字符转移到边的终点。
此外NFA还可以包含标有ε的边，这种边表示不需要任何字符就可以直接进行状态的转移。
容易想到，如果我们建立了一个只接受符合正则表达式的自动机，就可以通过它来较快的判断哪些位置是可匹配的。
具体应用
比较常见的字符串匹配自动机大多都是DFA。但是由于有+，*，把正则表达式直接转变成DFA是非常困难的。因此我们只能先把它转化成NFA。
先看一下一般的转换规则：
如果正则表达式是一个字符，那么对应的NFA是：
p0-a->p1
如果正则表达式是A+B的形式，那么只要把它们的起始状态和终止状态合并就可以：
p0-a->p1
p0-b->p1
如果正则表达式是AB的形式，那么只要把A和B对应的自动机首尾相接：
p0-a->p1-b->p2
如果正则表达式是A*的形式，那么就需要按下面的图来进行处理：
p0-a->p0
p0->p1
通过上面的步骤可以得出：NFA的状态数不会超过正则表达式长度。
NFA中的状态转移
在NFA中进行状态转移比DFA要困难一些。我们可以定义两个函数，一个叫做epsilon-closure，用来计算一组NFA状态通过epsilon边能够到达的NFA状态集合。另外一个move用来在NFA上进行状态的转移。
设当前的状态集合是now，那么状态转移的过程就是：
new = {}
for every state s in now do
new = new ∪ {t | (s,t) = c}
new = epsilon_closure(new)
其中的(s,t)=c表示从s状态经过一个字符c可以转化到t状态。因为这个语句需要的集合总数也不会太多，所以可以通过预先计算出它们来加快速度。预处理后这个过程的复杂度是O(m2)，而系数是比较小的。
但是由于在NFA中，我们必须把状态的集合作为一个真正的状态，每次状态转移都是对这个集合的处理。这样转移一次的复杂度是O(m2)，这是不可忍受的（最大的数据需要大约2分钟才能出解）。
既然NFA速度过慢，我们自然想要把它转化为DFA。因为DFA中的状态转移是O(1)的。可是并没有一个多项式复杂度的方法可以把NFA转换成DFA。一般介绍的NFA转换到DFA的方法都是通过类似BFS的方法来把NFA中所有可能出现的状态集合对应成DFA的一个状态。
这种转换在本题中显然是不可行的，因为NFA的结点数最多是500，而转化成的DFA则可能有多达2500个状态，即使实际有许多状态不能达到，也是无论如何不可以忍受的。
看来把NFA转换成DFA是行不通的。但是我们还是从NFA转DFA的过程中受到了一些启发：NFA之所以速度慢，是因为我们在进行状态转移的时候可能进行许多重复操作：比如从{1,2}沿一个字符1转移后是{2,3}，以后我们还可能遇到相同的情况，而这时我们还会用O(m2)的时间去进行状态转移。这是一种很严重的浪费。因此我们每进行一次状态转移，就把这个状态转移的情况放到hash表中，以后使用的时候就可以查找了。这相当于只把我们需要的一部分子集转移成DFA，虽然一般情况下并不能降低时间复杂度，但是在实际应用中确实很有效。（特别是对于没有*和括号的自动机，这样做可以保证线形的时间复杂度）
算法回顾和细节
我们重新来看一下算法的框架：
根据正则表达式建立NFA
now = start
while not eof do begin
read(c);
if 曾经进行过now,c的转移 then 利用以前的结果
else 进行状态转移并记录结果
if 终止状态 in now then 输出当前位置
end
建立NFA有各种方法，由于NFA并不会很大，所以我们可以使用递归的方法来实现。为了尽量减小系数，我们使用位压缩的方式来实现集合，并采用较为简化的hash函数（比如把一个集合位压缩后的一系列整数加起来取对220的余数），并在输入和输出的时候通过缓冲区来加快速度。这样就基本可以达到题目的时间要求。
但是注意到字符串可能有10M，而产生的NFA的状态集合最多也可能有10M个，而每个集合都需要100到200字节的存储空间，大大超出了允许的空间范围。因此我们需要对hash表的规模加以严格限制。如果规模过大就不得不放弃存储状态的想法，牺牲一定的时间来换取空间。
7. 算法设计题
1.遍历字符串，如果遇到“（”字符则把“（”push入栈，如果遇到“）”字符则pop，（pop前检查栈是否为空，如果为空则停止遍历，返回0）。便利完后检查栈是否为空，如果为空返回1，否则返回0。
2.用两个指针p1,p2。p1开始向后移动（p1=p1->next），等p1移动到k个元素时p2开始移动，以后p1,p2同步向后移，等p1移动到尾节点时（即p1->next==NULL)停止，此时p2所指即倒数第k个节点。
8. 影响算法设计的因素有哪些
影响算法设计的有以下因素：
针对机器：空间复杂性和时间复杂性。
针对程序员：算法表达和实现的简单性。
针对问题：算法对问题及问题输入规模的普适性。
影响算法效率的因素
1、从大的方面来讲，所选择的语言对算法的效率影响很大。一般来说，使用越高级的语言所需要的时间和空间就越大。另外，不同编译器产生的代码质量不同，这对算法的效率也会有影响。
2、存储结构
数据的存储结构，分为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；链式存储结构则是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。不同的问题求解选用不同的存储结构。
3、指针操作
在使用指针时，指针的有秩序扫描非常重要。例如在模式匹配中，如果直接进行匹配，当有不完全匹配时，主串的指针需要回溯。
在KMP算法中，我们先可以求出每个元素的next函数值，从而在发生不完全匹配时，主串的指针不必要回溯，只需要模式串的元素回到当前元素的next函数值所指的元素再进行匹配即可。当主串和模式串有很多不完全匹配时，KMP算法可以大大提高效率。
4、查找的效率
有很多快速查找的算法都可以提高查找的效率，如建立索引，折半查找等，都是在记录和关键字之间进行比较，从而寻求关系。这一类查找建立在比较的基础之上。查找的效率依赖于查找过程中所进行的比较次数。
在哈希表中，使得记录的存储位置和关键字之间建立一个确定的存储关系，因而在查找时，只需要根据这个对应的关系f 找到给定值K 的像f(k)。用这个思想建立哈希表。如在基因组匹配时，用哈希表非常方便。
5、数据类型的选择
数据类型的选择也会影响算法效率，在对时间和空间要求非常严格时，尽可能的使用占用空间较小的数据类型。使用动态开辟空间会使得效率降低，所有在能确定或估计出需要的空间大小的情况下尽量使用静态数字。个人觉得用vector虽然方便，但是效率并不高。
6、存储方式
用堆操作还是用栈操作，对于不同的问题需要仔细选择。在串和队列的有关操作中用堆操作合适，在树的操作中用栈操作合适，如建立二叉树中序遍历的递归算法或非递归算法，用栈操作好。
9. C语言程序设计，初级的~设计算法输入一个四位正整数，将它们倒排，例如输入1234，输出4321
“希望写的详细些，我就可以直接打上去了，连空格啊，标点啊也写一下.”....学习不是这样的。念亮。。。
给个思路就行了。用除法求出千位、求余再除法求出百位、再除法+求余求出十位，最后用求余得到个位。然后告宏按照个位十位百位千位一个一个袜高册输出即可。
10. 算法设计题：输入一个任意的非负数十进制整数，输出与其等值的八进制数
最近好多这样的问题哦，如果不能用%o来输出的话，那么一个很好的方法就是用堆栈，我用的是链式堆栈：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int DataType;
#include "LSNode.h";
void main()
{
LSNode *head;
float a;//为了判断输入是否为整数而设的变量
int x,y;
StackInitiate(&head);//初始化
printf("请输入一个非负十进制整数： ");
scanf("告芹%f",&a);
x=(int)a;
if(x<0||x!=a){printf("您输入的是负数或小数！\n");return;}
do
{
y=x%8;//除携余8取余
if(StackPush(head,y)==0)//入栈所得余数y
{
printf("错误辩友滚！\n");
return;
}
x=x/8;//取得本循环的商数作为下一循环被除数
}while(x!=0);
printf("转换成八进制为： ");
while(StackNotEmpty(head))
{
StackPop(head,&x);//出栈，次序刚好与入栈时相反
printf("%d",x);//显示各位元素
}
printf("\n");
Destroy(head);//撤销链式堆栈
}
然后用堆栈还需要自己定义一个名为"LSNode.h"的头文件。其内容是：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct snode
{
DataType data;
struct snode *next;
}LSNode;
void StackInitiate(LSNode **head)
{
if((*head=(LSNode *)malloc(sizeof(LSNode)))==NULL)exit(1);
(* head)->next=NULL;
}
int StackNotEmpty(LSNode *head)
{
if(head->next==NULL)return 0;
else return 1;
}
int StackPush(LSNode *head,DataType x)
{
LSNode *p;
if((p=(LSNode *)malloc(sizeof(LSNode)))==NULL)
{
printf("内存空间不足无法插入！\n");
return 0;
}
p->data=x;
p->next=head->next;
head->next=p;
return 1;
}
StackPop(LSNode *head,DataType *d)
{
LSNode *p =head->next;
if(p==NULL)
{
printf("堆栈已空出错！");
return 0;
}
head->next=p->next;
*d=p->data;
free(p);
return 1;
}
int StackTop(LSNode *head,DataType *d)
{
LSNode *p=head->next;
if(p==NULL)
{
printf("堆栈已空出错！");
return 0;
}
*d=p->data;
return 1;
}
void Destroy(LSNode *head)
{
LSNode *p,*p1;
p=head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
}
编好了保存到与程序同个文件夹里就好了。