帮做算法题

Ⅰ 帮我解决一道C语言算法的问题

这是一个最大子序列和问题。通常用动态规划法解。至于动态规划的数学模型，懒得去查了，直接给你找了一个算法，你凑合看吧。

从整数序列头部开始扫描，假设现扫描到的位置为i，求取从0到i所有元素的和sum[i]，sum[i]取最大值的地方即为最大子序列的结束位置，设为a。从结束位置a向前扫描，找到第一个小于零的位置b，b+1就是最大子序列的开始位置。求从b+1到a位置的值即可得到最大子序列和。按此思路该算法时间复杂度为O(m+n)，其中m, n分别为最大子序列的长度、给定整数序列的长度。
改进：根据对上述算法的进一步分析，可以知道，最大子序列和中必然不存在前缀子序列小于0的情况，于是设一ThisSum用于指示当前子序列和。改进算法描述如下：从整数序列头部开始扫描，累加序列元素和ThisSum，若ThisSum<0，则停止累加子序列和，将ThisSum清零，并从下一位置重新开始累加ThisSum，否则将ThisSum与当前MaxSum比较，并更新MaxSum。此改进算法时间复杂度仅为O(n)，n为给定整数序列的长度。

int MaxSubsequenceSum3(const int A[], int N)

{

int ThisSum, MaxSum, i;

ThisSum = MaxSum = 0;

for(i = 0; i < N; i++)

{

ThisSum += A[i];

if(ThisSum > MaxSum)

MaxSum = ThisSum;

else if(ThisSum < 0)

ThisSum = 0;

}

return MaxSum;

}

Ⅱ 哪位高手会用电脑做算法（就是流程图）来帮帮忙吧！下面是两道题，能不能帮我设计出他的流程图多谢啦！

1，写个简单的啊
unsigned int num1,num2,num3;
for ( num1 = 0; num1<100; num1++)
{
for ( num2=0; num2<100; num2++)
{
for ( num3=0; num3<100; num3++)
{
if ( num3 + num2 + num1 == 100 && num1*5 + num2*3 + num3 / 3 == 100)
printf("num1 = %d,num2 = %d,num3 = %d",num1,num2,num3);
}
}
}
2.
int a,b,c;
int num;
for ( int i=100; i<1000; i++)
{
a = i / 100;
b = i / 10 % 10;
c = i % 10；
if ( a*a*a + b*b*b + c*c*c == i)
printf("%4d",i);
}

Ⅲ 麻烦你帮我做一道题，503，87，512，908，170，276，436，316，对这一序列进行冒泡排序（算法），

要想了解算法，请看下面 冒泡排序 1、排序方法 将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 （1）初始 R[1..n]为无序区。 （2）第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。 第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。 （3）第二趟扫描 扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上…… 最后，经过n-1 趟扫描可得到有序区R[1..n] 注意： 第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R上，结果是R[1..i]变为新的有序区。 2、冒泡排序过程示例 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程 3、排序算法 （1）分析 因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。 若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。 （2）具体算法 void BubbleSort(SeqList R) { //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j； Boolean exchange； //交换标志 for(i=1;i<n;i++){ //最多做n-1趟排序 exchange=FALSE； //本趟排序开始前，交换标志应为假 for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key<R[j].key){//交换记录 R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //发生了交换，故将交换标志置为真 } if(!exchange) //本趟排序未发生交换，提前终止算法 return； } //endfor(外循环) } //BubbleSort 4、算法分析 （1）算法的最好时间复杂度 若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值： Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为O(n)。 （2）算法的最坏时间复杂度 若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值： Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。 （3）算法的平均时间复杂度为O(n2) 虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。 （4）算法稳定性 冒泡排序是就地排序，且它是稳定的。 5、算法改进 上述的冒泡排序还可做如下的改进： (1)记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中，记住最后一次交换发生的位置lastExchange，（该位置之前的相邻记录均已有序）。下一趟排序开始时，R[1..lastExchange-1]是有序区，R[lastExchange..n]是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。具体算法【参见习题】。 (2) 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 能一趟扫描完成排序的情况： 只有最轻的气泡位于R[n]的位置，其余的气泡均已排好序，那么也只需一趟扫描就可以完成排序。 【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。 需要n-1趟扫描完成排序情况： 当只有最重的气泡位于R[1]的位置，其余的气泡均已排好序时，则仍需做n-1趟扫描才能完成排序。 【例】对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。 ②造成不对称性的原因 每趟扫描仅能使最重气泡"下沉"一个位置，因此使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。 ③改进不对称性的方法 在排序过程中交替改变扫描方向，可改进不对称性。

Ⅳ c++菜鸟算法一道题帮忙做一下---互质环

//circle.in 和 circle.out用记事本打开
#include<fstream>
#include<algorithm>
using namespace std;
bool test(int[],int);
void printa(int a[],int n);
bool hu(int a,int b)
{
while(a%b!=0)
{
int r=b;
b=a%b;
a=r;
}
return b==1;
}
int main()
{
int n;
ifstream in("C:\\circle.in",ios::in);
if(!in)
return -1; //没有找到输入文件
in>>n;
int *a=new int[n];
for(int i=0;i<n;i++)
in>>a[i];
printa(a,n);
delete[] a;
}
bool test(int a[],int n)
{
for(int i=0;i<n;i++)
{
if(hu(a[i],a[(i+1)%n])==false)
return false;
}
return true;
}
void printa(int a[],int n)
{
ofstream out("C:\\circle.out",ios::out);
sort(a,a+n);
do
{
if(test(a,n) == true)
{
(a,a+n,ostream_iterator<int>(out," "));
return;
}
}while(next_permutation(a,a+n));
out<<-1;
}

Ⅳ 算法简单题，请用C或java实现，有帮助必采纳！

public static void main(String[] args) {

/*
* 结束时间减去开始时间
*/

String start = "23:59:59";
String end = "01:02:03";

LocalTime startTime = LocalTime.parse(start);
LocalTime endTime = LocalTime.parse(end);

if (endTime.toSecondOfDay() < startTime.toSecondOfDay()) {
startTime = startTime.plusHours(12);
endTime = endTime.plusHours(12);
}

// 间隔
LocalTime interval = LocalTime.ofSecondOfDay(endTime.toSecondOfDay() - startTime.toSecondOfDay());

System.out.println(interval);

System.out.println(interval.getHour());
System.out.println(interval.getMinute());
System.out.println(interval.getSecond());

}

Ⅵ 求帮算法作业！用动态规划法求解最长路径问题

先对图进行拓扑排序 一个结果为s b a c d t 拓扑排序的时候初始化dist[i] 表示从s到i的距离
dist[i]=max{dist[u]+edge[u][i], dist[i]}.
i从s取到t 最终得结果

Ⅶ 求数据结构与算法分析高人帮忙做下这几道题目。（希望能给出正确答案，在此谢过！！！）

填空题
1. n-1
因为队尾指针总是指向空。
2. 1
因为无向图的邻接矩阵是对称的。
3. 61
元素数量=
(rear+max-front) 当front > rear
(front+max-rear) 当rear > front
4. 深度优先搜索算法

5.

判断题
1. F
二叉树就可以用数组存储。
2. F
当发生冲突时，它要在下一个位置找，但如果该位置已被占用，仍需要继续向前。故同

义词不一定相邻。
3. F
图的邻接矩阵的行列数只取决于顶点数量。
4. F
没有最快的排序算法，只有特定条件下的相对较快。
5. T

选择题
1. D
2. B
Loc(a[6]) = Loc(a[1]) + (6-1)*2
= 90 + 10 =100
3. A
4. C
5. C
进堆排序时，每个元素在最底下的叶子层都有，然后较大的非叶子结点存储。

6. C
构造一棵二叉树：
/
* +
A + - F
B C D E
对该二叉树进行后序遍历即可。

7. C
折半查找要求查找表有序，并且可以根据下标定位，要求是直接存取。
顺序存储方式：可直接存取，但插入删除需耗时间
链式存储方式：只能顺序存取，插入删除方便

8. D
二次探测再散列法：
addr(key) = (初始哈希值+di)%表长
di=1、-1、4、-4、9、-9...

addr(15) = 15 % 11 = 4
addr(38) = 38 % 11 = 5
addr(61) = 61 % 11 = 6
addr(84) = 84 % 11 = 7

addr(49) = 49 % 11 = 5 有冲突
addr(49) = (5+1)%14=6 有冲突
addr(49) = (5-1)%14=4 有冲突
addr(49) = (5+4)%14=9

9. D
执行p的后继指针(next)指向p的直接后继结点(next)的下一个结点(next)即可

Ⅷ 跪求高人帮写下下面这道算法题。或者提供点思路。

作者：Wei.SteVe

1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4
5 /*---------------------------
6 函数需要进行不同字符串的匹配
7 本程序构造一个52个孩子结点的“字典树”
8 字典数的孩子编号通过getIndexByChar()函数获得
9 a b c d……A B C……X Y Z
10 用于快速的对子串匹配工作
11 ---------------------------*/
12
13
14 //构造一个字典数结点
15 struct Node
16 {
17 int value;//纪录树根到此结点的权值
18 Node* next[52];//26*2个字母所对应的下结点
19 };
20
21 //全局变量声明区
22 Node root;
23 char line[100];//存放从文件中读取得数据，然后进行处理对树的维护
24 FILE* stream;//文件描述符
25 char strTo[100];//读取被分析的字符串
26 int var[100];//代表dfs不同深度在字符串串中的间隔长度
27 int varValue[100];
28
29
30 //进行内存的初始化
31 void memNext(Node* r)
32 {
33 for(int i=0;i<52;i++)
34 {
35 r->next[i]=NULL;
36 }
37 }
38
39 //根据字符来获得其索引
40 int getIndexByChar(char t)
41 {
42 if(t>='a'&&t<='z')
43 return t-'a';
44 else if(t>='A'&&t<='Z')
45 {
46 return t-'A'+26;
47 }
48 else
49 return -1;
50 }
51
52 //向数据字典数中插入一条信息
53 void insertItem(char* line)
54 {
55 char st[50];
56 int v;
57 sscanf(line,"%s%d",st,&v);
58 int len=strlen(st);
59 Node* tNode=&root;
60 Node* newNode;
61 char c;
62 for(int i=0;i<len;i++)
63 {
64 c=line[i];
65 if(tNode->next[getIndexByChar(c)]!=NULL)
66 {
67 tNode=tNode->next[getIndexByChar(c)];
68 }
69 else
70 {
71 //新建结点
72 newNode=(Node*)malloc(sizeof(Node));
73 newNode->value=0;
74 memNext(newNode);
75 tNode->next[getIndexByChar(c)]=newNode;
76 tNode=newNode;
77 }
78 }
79 tNode->value=v;
80 }
81
82 //利用递归方法进行内存的释放
83 void deleteNode(Node* node)
84 {
85 if(node!=NULL)
86 {
87 for(int i=0;i<52;i++)
88 {
89 deleteNode(node->next[i]);
90 }
91 free(node);
92 }
93 }
94
95
96 //获取数中对应的权值，不是一个短语则为-1，0代表没这个短语
97 int getValue(char* s)
98 {
99 Node* t=&root;
100 int len=strlen(s);
101 for(int i=0;i<len;i++)
102 {
103 if(t->next[getIndexByChar(s[i])]!=NULL)
104 {
105 t=t->next[getIndexByChar(s[i])];
106 }
107 else
108 {
109 return -1;
110 }
111 }
112 return t->value;
113 }
114
115 //对数据进行处理，试探性的处理,depth代表dfs匹配的深度
116 void dfs(char* str,int depth)
117 {
118 int len=strlen(str);//取得当前点后还有多少字符
119 char* p=strTo;//指针，对字符串进行指示
120 //0个字符，代表已经成功完成，现在要进行显示
121 if(len==0)
122 {
123 int sum=0;
124 for(int i=0;i<depth;i++)
125 {
126 for(int j=0;j<var[i];j++)
127 {
128 printf("%c",*(p++));
129 }
130 putchar(' ');
131 sum+=varValue[i];
132 }
133 printf(" %d\n",sum);
134 }
135 Node* node=&root;
136 {
137 for(int i=0;i<len;i++)
138 {
139 if(node->next[getIndexByChar(str[i])]!=NULL)//不为空，则可以分割
140 {
141 if( node->next[getIndexByChar(str[i])]->value!=0)
142 {
143 var[depth]=i+1;//保存需要间隔的长度
144 varValue[depth]=node->next[getIndexByChar(str[i])]->value;
145 dfs(&str[i+1],depth+1);
146 }
147 node=node->next[getIndexByChar(str[i])];
148 }
149 else
150 {
151 return;
152 }
153 }
154 }
155 }//
156
157 int main()
158 {
159
160 //初始化root中的数值
161 memNext(&root);
162 if((stream = fopen( "BaseString.txt", "r" )) != NULL)
163 {
164 while(fgets( line, 100, stream ) != NULL)
165 {
166 //对字典数进行维护
167 insertItem(line);
168 }
169 }
170
171 scanf("%s",strTo);//读取待分析的字符串
172
173 //printf("%d\n",getValue("bc"));
174
175 dfs(strTo,0);//0代表dfs深度
176
177 for(int i=0;i<52;i++)
178 deleteNode(root.next[i]);
179 return 1;
180 }

Ⅸ 帮忙看看一个算法设计题，用C语言实现

//排序思想是一轮快速排序
#include<stdio.h>
#include<stdlib.h>
typedefstructaa
{
intdate[100];
inttop;
}aa,*pa;
pacreat()
{
paa=(aa*)malloc(sizeof(aa));
if(a)
a->top=0;
}
voidshow(paa)
{
inti;
printf("
线性表的元素是
");
for(i=0;i<a->top;i++)
{
printf("%-3d",a->date[i]);
if((i+1)%10==0)
printf("
");
}
}
voidinput(paa,intn)
{
if(a->top>=99)
printf("元素个数已满
");
else
{
a->date[a->top]=n;
a->top++;
}
}
voidchange(paa)
{
inti,key=a->date[0],low=0,hight=a->top-1;
while(low<hight)
{
while(key>a->date[low]&&low<=hight)
low++;
while(key<a->date[hight]&&hight>=low)
hight--;
i=a->date[low];
a->date[low]=a->date[hight];
a->date[hight]=i;

}
a->date[low]=key;
}
intmain()
{
inti,j,k,n;
paa=creat();
printf("请输入元素的个数
");
scanf("%d",&n);
printf("请输入这些互不相等的元素
");
for(i=0;i<n;i++)
{
scanf("%d",&k);
input(a,k);
}
show(a);
change(a);
show(a);
free(a);
return0;
}

Ⅹ 求高手帮忙做一套算法分析的题目。做好之后再加100。

如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？
排序：排序的循环次数（或递归次数）。
矩阵相乘：做实数乘法的次数。
树：搜索的次数。
图：同树。
算法有几种基本结构？各种结构的时间复杂度的计算规则？
3种
顺序结构：T(n)=O(c)
选择结构：T(n)=O(c)
循环结构：T(n)=O(n)
最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？
在规模n的全部输入中，可以找寻执行一个算法所需的最大时间资源的量，这个量称为对规模n的输入，算法的最坏情况时间复杂性。
对规模都为n的一些有限输入集，执行算法所需的平均时间资源的量称为平均情况下的时间复杂性。
为什么选择时间复杂度的渐进性态评价算法？
因为在规模较小的时候无法客观体现一个算法的效率。
解释f(n)=O(g(n))的意义。
若f(n)和g(n)是定义在正整数集合上的 两个函数，则f(n)=O(g(n))表示存在正的常数C和n0 ,使得当n≥n0时满足0≤f(n)≤C*g(n)。
简述之就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
有效算法和无效算法的划分原则？
区分在于问题是否能够精确求解。
用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？
分治法可以将问题分为许规模更小的子问题，这些子问题相互独立且与原问题相同。使用递归技术，虽然一些简单的循环结构替代之，但是复杂的问题，比如二阶递归是无法替代的。
归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？
归并排序算法：
划分子问题：每次分成2个大小大致相同的子集和
合并子问题：将2个排好序的子数组合并为一个数组
快速排序算法：对输入的子数组a[p:r]
划分子问题：划分为a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小于a[q]，a[q+1:r] 任意元素大于a[q]
合并子问题：不需要（因为划分过程就已经排序完成了）
简述二分检索（折半查找）算法为什么比顺序查找的效率高？
对于二分搜索 最坏情况为O(logn)时间完成
而顺序查找 需要O(n)次比较
显然二分搜索效率高
贪心法的核心是什么？
贪心算法是通过一系列选择得到问题的解，它所作出的选择都是当前状态下的最佳选择。
背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？ 用贪心算法解0/1背包问题是否可获得最优解？
Max=∑Vi*Xi (V是价值X取1，0表示装入或不装)
每次选取单位重量价值最高的
不一定是最优解

情况不妙啊 LZ还要继续否。。。
早知发邮件了。。。