存儲量的存在意義是什么

就是用來存儲某一種信息或者問題求解時的某一種狀態，以方便程序在需要回溯信息的時候加以利用。

題目1：必要的存儲量

以下哪些可以不借助數組，那些必須借助數組？也就是一個關于求解數據和輸入數據之間的獨立性問題。

-1 統計個數、

-2求max,min,average、

-3 求哪兩個數最接近、

-4 求第二大的值、

-5 求方差、

-6 統計不超過平均數的個數

我將這類題分為兩類：
1.依賴于當前狀態
2.依賴于（所有）輸入數據

1.依賴當前狀態

對于第1.2.4問，只需要在輸入數據的時候讀取一次數據信息，信息的傳遞是連續性的，不需要回溯已輸入數據就可以實現相應功能。
比如統計功能，輸入數據的同時進行統計，當輸入下一個數據時，已經不需要再考慮前面的數據信息的影響了，因此不需要數組來額外存儲數據信息。

2.依賴于（所有）已輸入數據

以方差為例，方差的計算主要分為兩步，第一步，通過讀取輸入數據獲得平均值，第二步，通過方差公式求解方差，方差公式要用到已輸入數據X和均值μ，即第二步依賴于第一步獲取的平均值信息和輸入數據信息。平均值可以在完第一步之后即時獲得，然而在不利用數組存儲的情況下，輸入數據在輸入下一個數據時就已經丟失了。

關于其他幾問

關于第3問，由于需要回溯之前輸入的數據，以判斷兩個數的接近程度，因而需要數組的輔助，我之前看到一篇博客3.4.2 題目1 必要的存儲量說不需要數組，其中代碼只考慮到已經輸入的前三個數據的狀態，而忽視了一個問題，存在這樣一種情況，如果第四個數據和第三個數據最接近，但是由于第三個數據和前面兩個數據的接近值相比并不是最接近的而導致第三個數據的信息被舍棄了，這樣反而無法得到正確答案：實際上最接近的是第三個第四個數據。用 4 8 13 14這個輸入數據測試一下就知道了。

像是求第二大的值，這類問題，最大值和第二大值的關系如何理解是關鍵，像之前那些需要數組存儲的問題，一個關鍵點在于，它們的數據處理，我稱之為所求數據的獨立性，像是方差，它和輸入數據的關系并不獨立，多一個輸入數據，方差又需要重新計算平均值，重新利用方差公式計算求解。而第二大值問題，很明顯，第二大值是相對比較獨立的，當數據輸入后就不再依賴于之前已輸入的數據了，對于新輸入的數據，要么讓它更大（等于新輸入數據或者新輸入數據比最大值大，也就是，空降一個二大王或者大王被降職當二大王了…），要么不變（嘍啰不需要名字…），就這兩種狀態變化。最大值和二大值明顯依賴于當前狀態就可以獲得，對于一個新輸入的值，不需要拿他和已經輸入的數據進行比較，只需要拿他和當前的最大值以及二大值比較即可，無須存儲已輸入的數據信息。

#include <stdio.h> #include <limits.h> int main() {int n,max=INT_MIN,smax=INT_MIN;while(scanf("%d",&n)==1&&n){if(max<n){smax=max;max=n;}if(n>smax&&n<max)smax=n;}printf("Max:%d SecondM:%d\n",max,smax);return 0; }

總結

以上是生活随笔為你收集整理的关于算法竞赛入门经典3.4.2思考题题目1必要的存储量的思考的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。