1、找到滿足條件的數(shù)組
給定函數(shù)d(n)=n+n的各位之和，n為正整數(shù)，如d(78)=78+7+8=93。這樣這個(gè)函數(shù)可以看成一個(gè)生成器，如93可以看成由78生成。
定義數(shù)A：數(shù)A找不到一個(gè)數(shù)B可以由d(B)=A，即A不能由其他數(shù)生成?，F(xiàn)在要寫程序，找出1至10000里的所有符合數(shù)A定義的數(shù)。
回答：
申請(qǐng)一個(gè)長(zhǎng)度為10000的bool數(shù)組，每個(gè)元素代表對(duì)應(yīng)的值是否可以有其它數(shù)生成。開(kāi)始時(shí)將數(shù)組中的值都初始化為false。
由于大于10000的數(shù)的生成數(shù)必定大于10000，所以我們只需遍歷1到10000中的數(shù)，計(jì)算生成數(shù)，并將bool數(shù)組中對(duì)應(yīng)的值設(shè)置為true，表示這個(gè)數(shù)可以有其它數(shù)生成。
最后bool數(shù)組中值為false的位置對(duì)應(yīng)的整數(shù)就是不能由其它數(shù)生成的。
2、實(shí)現(xiàn)一個(gè)函數(shù)，對(duì)一個(gè)正整數(shù)n，算得到1需要的最少操作次數(shù)。操作規(guī)則為：如果n為偶數(shù)，將其除以2;如果n為奇數(shù)，可以加1或減1;一直處理下去。
例子：
func(7) = 4，可以證明最少需要4次運(yùn)算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：實(shí)現(xiàn)函數(shù)(實(shí)現(xiàn)盡可能高效) int func(unsign int n);n為輸入，返回最小的運(yùn)算次數(shù)。給出思路(文字描述)，完成代碼，并分析你算法的時(shí)間復(fù)雜度。
答：
假設(shè)n表示成二進(jìn)制有x bit，可以看出計(jì)算復(fù)雜度為O(2^x)，也就是O(n)。
將n轉(zhuǎn)換到二進(jìn)制空間來(lái)看(比如7為111，6為110)：
- 如果最后一位是0，則對(duì)應(yīng)于偶數(shù)，直接進(jìn)行除2操作。
- 如果最后一位是1，情況則有些復(fù)雜。
**如果最后幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應(yīng)該-1;在第二種情況下-1和+1最終需要的步數(shù)相同。所以在???01的情況下，應(yīng)該選擇-1操作。
**如果最后幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數(shù)相同;在第二種情況下+1步數(shù)更少些。所以在???011的情況下，應(yīng)該選擇+1操作。
**如果最后有更多的連續(xù)1，也應(yīng)該選擇+1操作。
如果最后剩下的各位都是1，則有11時(shí)應(yīng)該選擇-1;111時(shí)+1和-1相同;1111時(shí)應(yīng)選擇+1;大于四個(gè)1時(shí)也應(yīng)該選擇+1;
由以上的分析可知，奇數(shù)的時(shí)候加1或減1，完全取決于二進(jìn)制的后兩位，如果后兩位是10、00那么肯定是偶數(shù)，選擇除以2，如果后兩位是01、11，那么選擇結(jié)果會(huì)不一樣的，如果是*****01，那么選擇減1，如果是*****11，那么選擇加1，特殊情況是就是n是3的時(shí)候，選擇減1操作。
給定函數(shù)d(n)=n+n的各位之和，n為正整數(shù)，如d(78)=78+7+8=93。這樣這個(gè)函數(shù)可以看成一個(gè)生成器，如93可以看成由78生成。
定義數(shù)A：數(shù)A找不到一個(gè)數(shù)B可以由d(B)=A，即A不能由其他數(shù)生成?，F(xiàn)在要寫程序，找出1至10000里的所有符合數(shù)A定義的數(shù)。
回答：
申請(qǐng)一個(gè)長(zhǎng)度為10000的bool數(shù)組，每個(gè)元素代表對(duì)應(yīng)的值是否可以有其它數(shù)生成。開(kāi)始時(shí)將數(shù)組中的值都初始化為false。
由于大于10000的數(shù)的生成數(shù)必定大于10000，所以我們只需遍歷1到10000中的數(shù)，計(jì)算生成數(shù)，并將bool數(shù)組中對(duì)應(yīng)的值設(shè)置為true，表示這個(gè)數(shù)可以有其它數(shù)生成。
最后bool數(shù)組中值為false的位置對(duì)應(yīng)的整數(shù)就是不能由其它數(shù)生成的。
2、實(shí)現(xiàn)一個(gè)函數(shù)，對(duì)一個(gè)正整數(shù)n，算得到1需要的最少操作次數(shù)。操作規(guī)則為：如果n為偶數(shù)，將其除以2;如果n為奇數(shù)，可以加1或減1;一直處理下去。
例子：
func(7) = 4，可以證明最少需要4次運(yùn)算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：實(shí)現(xiàn)函數(shù)(實(shí)現(xiàn)盡可能高效) int func(unsign int n);n為輸入，返回最小的運(yùn)算次數(shù)。給出思路(文字描述)，完成代碼，并分析你算法的時(shí)間復(fù)雜度。
答：
假設(shè)n表示成二進(jìn)制有x bit，可以看出計(jì)算復(fù)雜度為O(2^x)，也就是O(n)。
將n轉(zhuǎn)換到二進(jìn)制空間來(lái)看(比如7為111，6為110)：
- 如果最后一位是0，則對(duì)應(yīng)于偶數(shù)，直接進(jìn)行除2操作。
- 如果最后一位是1，情況則有些復(fù)雜。
**如果最后幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應(yīng)該-1;在第二種情況下-1和+1最終需要的步數(shù)相同。所以在???01的情況下，應(yīng)該選擇-1操作。
**如果最后幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數(shù)相同;在第二種情況下+1步數(shù)更少些。所以在???011的情況下，應(yīng)該選擇+1操作。
**如果最后有更多的連續(xù)1，也應(yīng)該選擇+1操作。
如果最后剩下的各位都是1，則有11時(shí)應(yīng)該選擇-1;111時(shí)+1和-1相同;1111時(shí)應(yīng)選擇+1;大于四個(gè)1時(shí)也應(yīng)該選擇+1;
由以上的分析可知，奇數(shù)的時(shí)候加1或減1，完全取決于二進(jìn)制的后兩位，如果后兩位是10、00那么肯定是偶數(shù)，選擇除以2，如果后兩位是01、11，那么選擇結(jié)果會(huì)不一樣的，如果是*****01，那么選擇減1，如果是*****11，那么選擇加1，特殊情況是就是n是3的時(shí)候，選擇減1操作。