日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

對于一個(gè)由0…n的所有數(shù)按升序組成的序列，我們要進(jìn)行一些篩選，每次我們?nèi)‘?dāng)前所有數(shù)字中從小到大的第奇數(shù)位個(gè)的數(shù)，并將其丟棄。重復(fù)這一過程直到最后剩下一個(gè)數(shù)。請求出最后剩下的數(shù)字。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊、網(wǎng)頁空間、營銷軟件、網(wǎng)站建設(shè)、涿鹿網(wǎng)站維護(hù)、網(wǎng)站推廣。

輸入描述:

每組數(shù)據(jù)一行一個(gè)數(shù)字，為題目中的n(n小于等于1000)。

輸出描述:

一行輸出最后剩下的數(shù)字。

輸入例子:

500

輸出例子：

255

方法一：常規(guī)解法，將數(shù)組不斷更新，每一次去除奇位數(shù)的元素，直至數(shù)組的長度為1，輸出即可。
算法復(fù)雜度：
T（n） = n + n/2 + n/4 +…1 = 2^n-1
故為O（2^n）
時(shí)間復(fù)雜度：
O(n)
代碼：（偷個(gè)懶寫個(gè)python版）

n = int(input())
lis = [i for i in range(0,n+1)]
while len(lis)!=1:
    lis = [i for i in lis if (lis.index(i)+1)%2==0]
print(lis)

方法二：利用二進(jìn)制巧妙解法
思路：
我們發(fā)現(xiàn)，每一次刪除的元素都是對應(yīng)下標(biāo)位置的二進(jìn)制最右端為0的元素，列如0（二進(jìn)制為0），2（二進(jìn)制為10），4（二進(jìn)制為100）。剩余的元素例如1（01），3（11），5（101）在下一次的變換中對應(yīng)的二進(jìn)制下標(biāo)為原二進(jìn)制下標(biāo)左移一位之后的1（1），3（10），5（10）之后繼續(xù)刪除對應(yīng)下標(biāo)的二進(jìn)制數(shù)的最右端為0的元素。所以最后剩下的元素，一定是從右往左數(shù)二進(jìn)制數(shù)中含1最多的元素，因?yàn)槊恳淮蝿h除移位后最右端都為1，會(huì)被一直保留下來
算法復(fù)雜度：
O(n)
空間復(fù)雜度:
O(1)

#includeusing namespace std;
int main(){int n;
	cin>>n;
	int x = 1;
	while( x<= n )
		x = x*2 +1;
	cout<< (x>>1)<< endl;
}

方法三：數(shù)學(xué)公式法
分析可知，每一次減少一半的數(shù)據(jù)，經(jīng)過long(n)（向下取整）次減少到只有一個(gè)數(shù)。那么只有2^floor(log(n)) 或者 2^floor(log(n))-1 能夠經(jīng)過long(n)次的向下取整之后得到1.因?yàn)樵诘谝淮蝿h除時(shí)，已經(jīng)去除所有的偶數(shù)，因此排除2^{log(n))。所以這個(gè)數(shù)為2}log(n))-1
算法復(fù)雜度：
時(shí)間復(fù)雜度：O（1）
空間復(fù)雜度：O(1)

#includeusing namespace std;
int main(){int n;
	cin>>n;
	cout<<(int)pow(2,floor(log2(n)))-1<