幫做演算法題

Ⅰ 幫我解決一道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還要繼續否。。。
早知發郵件了。。。