❶ c語言，最長上升子序列數,,
最長上升子序列（LIS）
問題描述：設現在有一串序列，要求找出它的一串子序列，這串子序列可以不連續，但必須滿足它是嚴格的單調遞増的且為最長的。把這個長度輸出。
示例：1 7 3 5 9 4 8 結果為4
題例：參看POJ 2533
解法：
1. DP之O(n2)演算法：先按DP的思想來分析一下，要想求n個數的最長上升子序列，設有數據數組data[n]和狀態數組dp[n]，則對其尾元素data[n]來說，它的最長上升子序列就是它自己，即dp[n]=1，而當把它的前一個元素data[n-1]考慮進來時，如果data[n-1]<data[n]則會存在一個長度為2的上升子序列，如果data[n-1]>data[n]那麼這個長度仍會是1。當把這個思想一般化的時候，對於任意一個元素data[k]來說，我們需要找出在data[k]以後的元素中比data[k]大，並且最長的一個序列做為它的後繼。這樣dp[k]就可以寫成dp[k+1]+1。現在我們定義一個量dp[k]=m，它代表著到第k個元素為止（可以包含k也可以不包含k），它的最長上升序列的長度為m。仔細體會dp[k]=m的意義，這裡面的k是可包括在內，也可以不包括在內的（與之前的最大子序列和不同）。要想確定這個m的值，就必須找到一個在第k個元素之前的一個元素的值小於data[k]的值，並且那個元素所對應的dp值是找到的滿足第一個條件前提下dp值最大的一個。這就意味著我們需要內層遍歷之前算出來的dp值，所以需要兩層循環來實現這個演算法。這樣我們就可以總結出狀態轉移方程為dp[k]=max(dp[i](1<=i<=k&&a[i]<a[k])+1。其中找dp[i]的過程我們需要用一層循環來實現，而找dp[k]的過程也要一層循環，所以我們得到了O(n2)的演算法。
dp[k]=max(dp[i])+1 其中i滿足(1<=i<=k&&a[i]<a[k])
常式：
#include <stdio.h>
const int inf = -0x3fffffff;
int main(void)
{
int i,j,len,max,res,data[] = {1,7,3,5,9,4,8},dp[20]={1};
len = sizeof(data)/sizeof(int);
res = max = inf;
for(i=1;i<len;i++)
{
max = inf;
for(j=0;j<=i;j++)
if(data[i]>data[j]&&max<dp[j])
max=dp[j];
dp[i]=max+1;
if(res<dp[i])
res = dp[i];
}
printf("%d\n",res);
return 0;
}
❷ 求問C語言：簡易版最長序列
#include<stdio.h>
voidfun()
{
intn,m,max=0,a[10]={0};
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
a[m]++;
}
for(m=0;m<10;m++)
if(a[m])
{
if(a[m]>max)
max=a[m];
}
for(m=0;m<10;m++)
if(a[m]==max)
printf("%d%d ",m,a[m]);
}
intmain()
{
intt;
scanf("%d",&t);
while(t--)
{
fun();
}
return0;
}
❸ 設計一個O（n的平方）時間的演算法，找出由n個數組成的序列的最長單調遞增子序列
用冒泡法 時間復雜度=O(n^2)
以 下是c語言版
#include <stdio.h>
main()
{int a[10];
int i,c,j;
for(i=0;i<10;i++)
{printf("請輸入十個數,這是第%d個:",i+1);
scanf("%d",&a[i]);
}
for(i=0;i<10;i++)
{
for(j=10;j>i+1;j--)
{if(a[j-1]<a[j-2])
{c=a[j-1];
a[j-1]=a[j-2];
a[j-2]=c;
}
}
}
printf("從小到大的順序是:");
for(i=0;i<10;i++)
{printf("\n%d",a[i]);
}
getch();
}
❹ c語言求最長遞增序列
int findLengthOfLCIS(int* nums, int numsSize){
if(numsSize <=1 )
{
return numsSize;
}
int ans, cnt, i;
ans = 1; //保存最長數
cnt = 1; //記錄最長數
for(i=0; i<numsSize-1; i++)
{
if(nums[i+1]>nums[i]) //如果遞增，計數加一，否則重新算起
{
cnt++;
}else{
cnt = 1;
}
ans = cnt>ans ? cnt: ans; //更新並保存之前最長數
}
return ans;
}
❺ c語言編寫 求一個數列中的最長子序列 數字可以不連續 如 輸入 8 4 5 7 6 1 輸出 4
無限不循環小數
❻ C語言求最長子序列
下面是你的代碼修改過後的結果，改過的地方都有注釋，另有測試樣例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最長子序列：9
4
-2 -3 8 -7
最長子序列：8
3
-2 -2 7
最長子序列：7
2
-1 5
最長子序列：5
1
-2
最長子序列：0
Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.
*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在這里再加一個判斷條件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是負數的話，結果應該是0，即一個都不選
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最長子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}
❼ C語言LCIS（最長公共上升子序列）（DP）如何列印解
用一個解向量存儲解啊，思路如下
function(..., char v[]) /*v用於存儲最優解的*/
{
......
if(當前解更優){
當前解為更優解;
更新向量v; /*最好附添加一個結束符*/
}
......
}
主函數中輸出解向量即可。
❽ 最長非降子序列 C語言
任意數列為a[n];
用b[n]來記錄最長遞增子序列的長度；
代碼如下：
int MaxSort()
{
int i, j, k;
for (i=1, b[0]=1; i<n; i++)
{
for(j=0,k=0; j<i; j++)
if (a[j]<=a[i] && k<b[j])
k = b[j];
b[i] = k+1;
}
//返回最大的b[i]
int tmp = 0;
for (int i=0; i<n; i++)
{
if (tmp < b[i])
tmp = b[i];
}
return tmp; //返回最長非降子序列的個數
}
***************************
如果是返回最長子序列，可以用容器：
vector<int > MaxSort()
{
int i, j, k;
for (i=1, b[0]=1; i<n; i++)
{
for(j=0,k=0; j<i; j++)
if (a[j]<=a[i] && k<b[j])
k = b[j];
b[i] = k+1;
}
//返回最大的b[i]的下標count
int count= 0, tmp = 0;
for ( i=0; i<n; i++)
{
if (tmp < b[i])
{
tmp = b[i];
count = i;
}
}
//定義vector,存最長非遞減子序列
vector<int> vec;
tmp = b[count];
for ( i=count; i>=0 ; i--)
{
if (tmp >= b[i])
{
vec.push_front(b[i]);
tmp = b[i];
}
else
break;
}
return vec;
}
❾ 求問c語言最長公共子序列代碼哪裡錯了！！！ 搞了好久，頭暈了都。 感覺是對的，就是不行。。。
樓主你好。
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
//下面兩行不怎麼需要，因為已經初始化為0了
for(i=0;i<m;i++) c[i][0]=0;//注意應該是從0到m-1
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){//這里注意應該是從1到m-1
for(j=1;j<n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){//這里注意是==，不是=
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列長度為%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}
你運行一下我的代碼，沒問題的。代碼中出現的問題我以注釋的形式寫出來了。
不過勸告樓主，以後寫代碼一定要多寫一些注釋。因為一般的程序員都能寫出機器能讀懂的代碼，而高級程序員才能寫出人也能讀懂的代碼。寫注釋很重要，顯示出代碼的思路。否則思路不清晰的高深代碼，一開始只有原作者和上帝能懂，過一段時間就只有上帝能懂了。
如果還有問題可以再問。
❿ 求最長公共子序列的C語言程序
得到字元串m1,m2後，有一個為空則子列為空。
如果都不為空，開始下面的步驟。
求得兩列的長度分別為n1,n2。
動態生n2行n1列矩陣（二維數組）。
取m2中每個元素（記位置為i）與m1中元素（記位置為j）逐個比較，如果相等則為矩陣中相應行列坐標的元素賦值為1，否則為0（可用循環嵌套完成）。
比如m1(abc0cbad)m2(cba1abc)兩串的話，可以得到如圖所示矩陣。
然後，不難看出，要進行如下步驟。
定義max,用來記錄最大子列中元素個數。
定義數組l[n2],用來記錄最大子列的首字元地址（因為可能有不同最大子列，故用數組，而不是單個變數）。
判斷矩陣中每一個元素，是否為1，如果是則記下此時行地址到l數組，然後判斷相對於這個元素的下一行下一列的元素是否為1，如果是則繼續判斷，一直到為0。記下此次判斷（即一個while循環）中「1」的個數n，存入變數max。
對於矩陣中的每一個元素都這么判斷，如果判斷中n的值大於max那麼把n付給max，同時把這個子列的首地址付給l[0]，l[0]後面的元素全賦值為-1。如果，某次判斷得到的n與max相同，即有相同最大子列，那麼把它的首地址存入l數組的下一個位置。
當這個矩陣的每一個元素都判斷完畢後，會得到max,和數組l，然後用循環做如下輸出過程：依次以l數組中的每個元素為首地址，輸出m2字元串中以相應序號開頭的max個字元，那麼完成所有最大子列的輸出。
昨天失眠了，一直到今天凌晨3點多，腦袋渾渾噩噩的，本想幫你敲代碼，可是腦力不支了，估計敲出來也亂，還有問題的話，再討論452032545