close
之前上學期末的一個問題：
Every sequence in R^k has monotone subsequence.
曾經考慮的想法是
suppose {Pn} be a seq which has no monotone increasing.
i.e {Qn} be subseq of {Pn}then
Q1
let W1 be first elt such that (1) happen.
if can`t find another elt s.t (1)happen.
then We only to choice {Qk}/{W1}
But it`s monotone increasing .-><-
so let W2 be 2rd elt such that (1) happen.
choice like previous.
then We have a subseq {W1,W2,.....}
但是卻不能確保Wi>Wi+1，目前還沒想到要怎麼修正..
以下這是在數學轉信版LPH提供的方法~~
首先取數列第一項
然後接著每次都取這之後比剛取的那一項大的項中的第一項
取到後面沒有比剛取的項大的項為止
這樣出來的數列是遞增
如果連子數列的第二項都找不到 也就是第一項是數列的最大值
那麼對去除第一項的數列 重覆取如一開始所說的遞增數列
取完後把數列到取到的地方之前的數丟掉繼續
一直取到不能再取為止
則這些遞增數列的末項(含第一項單獨形成第一個數列)形成遞減數列
接著今天劉老師給的想法
取整個數列中的最大數當第一項..
如果這數不存在，也就是此數列是發散..
隨便抓一項當子數列第一項，因為發散，一定有項比前面的項大..
這樣取下去，就創造了一組單調遞增子數列..
如果這數存在，選作第一項..接著扣除這項..找剩下數列中最大項作第2項..
依此類推取下去則找到一組遞減數列...
下面這兩個方法都是正面出發証...
希望能嘗試看看用反面來作
Every sequence in R^k has monotone subsequence.
曾經考慮的想法是
suppose {Pn} be a seq which has no monotone increasing.
i.e {Qn} be subseq of {Pn}then
Q1
let W1 be first elt such that (1) happen.
if can`t find another elt s.t (1)happen.
then We only to choice {Qk}/{W1}
But it`s monotone increasing .-><-
so let W2 be 2rd elt such that (1) happen.
choice like previous.
then We have a subseq {W1,W2,.....}
但是卻不能確保Wi>Wi+1，目前還沒想到要怎麼修正..
以下這是在數學轉信版LPH提供的方法~~
首先取數列第一項
然後接著每次都取這之後比剛取的那一項大的項中的第一項
取到後面沒有比剛取的項大的項為止
這樣出來的數列是遞增
如果連子數列的第二項都找不到 也就是第一項是數列的最大值
那麼對去除第一項的數列 重覆取如一開始所說的遞增數列
取完後把數列到取到的地方之前的數丟掉繼續
一直取到不能再取為止
則這些遞增數列的末項(含第一項單獨形成第一個數列)形成遞減數列
接著今天劉老師給的想法
取整個數列中的最大數當第一項..
如果這數不存在，也就是此數列是發散..
隨便抓一項當子數列第一項，因為發散，一定有項比前面的項大..
這樣取下去，就創造了一組單調遞增子數列..
如果這數存在，選作第一項..接著扣除這項..找剩下數列中最大項作第2項..
依此類推取下去則找到一組遞減數列...
下面這兩個方法都是正面出發証...
希望能嘗試看看用反面來作
全站熱搜
留言列表