By SmartPtr(http://m.shnenglu.com/SmartPtr/)
從0~13中任取出7個(gè)數(shù)，然后判斷這7個(gè)數(shù)中是否存在連續(xù)的5個(gè)數(shù)， 規(guī)則如下：
1) 7個(gè)數(shù)可以是重復(fù)的數(shù).
2) 0可以表示任意數(shù)
例子如下：
0, 1, 4, 3, 8, 0, 13--->true: 1-2-3-4-5
0, 1, 1, 1, 9, 10, 0--->false
0, 1, 3, 9, 10, 11, 12->true: 9-10-11-12-13
0, 0, 0, 0, 0, 0, 0->true: 0-1-2-3-4
這是最近看到的一個(gè)算法題， 粗粗一看，覺得很簡單， 可是慢慢往里面想，覺得要考慮的還是挺多的。現(xiàn)在把它實(shí)現(xiàn)出來放在這里，當(dāng)然，加了幾個(gè)參數(shù)使其更加通用。希望對(duì)大家有些參考價(jià)值。寫的不明白的地方，有錯(cuò)誤的地方大家可以指出來；大家如果有好的思路的話也希望能寫下來共享一下。以下是代碼與注釋：
#include <stdio.h>
#include <iostream>
using namespace std;
/*
從0~13中任取出7個(gè)數(shù)，然后判斷這7個(gè)數(shù)中是否存在連續(xù)的5個(gè)數(shù)， 規(guī)則如下：
1) 7個(gè)數(shù)可以是重復(fù)的數(shù).
2) 0可以表示任意數(shù)
例子如下：
0, 1, 4, 3, 8, 0, 13--->true: 1-2-3-4-5
0, 1, 1, 1, 9, 10, 0--->false
0, 1, 3, 9, 10, 11, 12->true: 9-10-11-12-13
0, 0, 0, 0, 0, 0, 0->true: 0-1-2-3-4
*/
// Helper functions
void outputarray(int a[], int n)
{
for(int i = 0; i < n; ++i) cout<<a[i]<<" ";
cout<<endl;
}
void outputresult(int nstart, int m)
{
cout<<"Continuous Array:";
while(m--) cout<<nstart++<<" ";
cout<<endl;
}
// Return if the n elements array contains m continuous numbers, the elements must large than 0
// this is a common implementation
bool Is_n_Contains_m_ContinuousNum(int a[], int n, int m)
{
// step 1: get num of 0
int nZeroNum = 0;
for(int i = 0; i < n; ++i)
if(0 == a[i]) ++nZeroNum;
cout<<"Original Array: "; outputarray(a, n);
// step 2: if we have enough 0, get continuous num is easy.
if(nZeroNum >= m-1)
{
int min = a[0];
for(int i = 1; i < n; ++i)
if(a[i] < min || 0 == min) min = a[i];
outputresult(min, m);
return true;
}
// not enough zero, we need to refine the judgement
else
{
// step 2.1: sort the array. (bubble sort, ascending)
bool bIsDone = false;
for(int i = n-1; i >= 0 && !bIsDone; --i)
{
bIsDone = true;
for(int j = 0; j < i; ++j)
{
if(a[j+1] < a[j])
{
bIsDone = false;
int tmp = a[j+1];
a[j+1] = a[j];
a[j] = tmp;
}
}
}
cout<<"Sorted Array: "; outputarray(a, n);
// step 2.2: remove redundant num except 0
int aa[256];
aa[0] = a[0];
int j = 1;
for(int i = 0; i < n-1; ++i)
{
if(a[i+1] != a[i] || 0 == a[i+1])
aa[j++] = a[i+1];
}
memcpy(a, aa, j * sizeof(aa[0]));
n = j;
if(n < m) return false;
cout<<"Unique Array: "; outputarray(a, n);
// step 2.3: get index of first non-zero element
int nIndex = 0;
for(int i = 0; i < n; ++i)
{
if(a[i] != 0)
{
nIndex = i;
break;
}
}
// step 2.4: refined judgement
// if n = 7; m = 5; nZeroNum = 2;
// if we can get continious number without zero or only with 1 zero, then with 2 zero is ok too.
// so if we got x zeros, we need to check if can success with (0 ~ x-1) zeros
for(int k = 0; k <= nZeroNum; ++k)
{
int nInterval = m - k - 1;
for(int i = nIndex; i < n-nInterval; ++i)
{
// when k = nZeroNum = 2;
// if the a[i+nInterval] - a[i] ranged in (nInterval, m-1), then it is continuous)
// means a[i+2] - a[i] ranged in (2, 4), for example:
// 1 3 5; 1 2 3; 1 2 4;
if(a[i+nInterval] - a[i] <= m-1 && a[i+nInterval] - a[i] >= nInterval)
{
outputresult(a[i], m);
return true;
}
}
}
}
return false;
}
int main(int argc, char *argv[])
{
int a[] = {0, 0, 0, 0, 0, 0, 0};
if(!Is_n_Contains_m_ContinuousNum(a, sizeof(a)/sizeof(a[0]),5))
cout<<"Continuous Array:Not Found ";
return 0;
}
PS：網(wǎng)友建議
fflush：不需要這么復(fù)雜吧，題目說明了是從0~13中任取出7個(gè)數(shù)，那么建立一個(gè)int A[13]，記錄哪些數(shù)有哪些數(shù)沒有（有的話置A[i]為1，否則是0），然后檢測A中連續(xù)的5個(gè)位置的情況就可以了
SmartPtr：fflush的思路對(duì)我很有啟發(fā)， 但我們還要考慮多個(gè)0的情況， 按著這個(gè)思路的話我覺得可以這么做：針對(duì)0～13建立一個(gè)數(shù)組A[14], A[0], A[1]...分別對(duì)應(yīng)0， 1...的個(gè)數(shù)。然后依次檢測A中連續(xù)的5個(gè)位置， 如果其0的個(gè)數(shù)小于A[0],那么就存在連續(xù)的數(shù)。（當(dāng)然還有一些邊緣情況要處理）。
這個(gè)算法我覺得十分有效， 通過引入一個(gè)數(shù)組大大的簡化了問題。但是有個(gè)缺點(diǎn)就是如果要判斷任意范圍內(nèi)的5個(gè)連續(xù)數(shù)就不容易了。如：
0， 1， 122， 678， 10000， 3， 6
posted on 2007-08-26 20:49
SmartPtr 閱讀(1122)
評(píng)論(0) 編輯 收藏 引用