• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			


            

            隨筆 - 51, 文章 - 1, 評論 - 41, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數據加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			兩道程序題目
		
            
		
            
		題一：找出字符串中最長的不重復的字母子串，字串不包括數字，區分大小寫。如：a123bcBdba最長的子串bcBd。

            分析：只考慮實現功能，較易實現。計算以src[i]為起始字母最大不重復子串的長度，找出最長的。

            char *max_uniq_sub(char* src)
            {
                            int i, j, t;
                char             *ret = 0;
                            int maxlen = 0;

                            for (i=0; src[i]!='\0'; i++)
                {
                                /* 是否為數字 */
                                if (src[i] >= '0' && src[i] <= '9')
                        continue;

                                for (j=i+1; src[j]!='\0'; j++)
                    {
                                    /* 是否為數字 */
                                    if (src[j] >= '0' && src[j] <= '9')
                            goto next;

                                    /* 是否與前面的重復 */
                                    for (t=i; t<j; t++)
                        {
                                        if (src[j] == src[t])
                                            goto next;
                        }
                    }
            next:        /* 子串結束，是否是最長的 */
                                if (j-i > maxlen)
                    {
                        ret             = src+i;
                        maxlen             = j-i;
                    }
                }

                return ret;
            }
            
這個算法的時間復雜度最差O(n^3)，最好O(n)。最差時的例子：當字符串就是非重復子串。最好是的例子：數字字符串或者一個元素重復的字符串。

            這個算法結構清晰，但有很多改進的地方。數據結構講過一種字符串子串匹配算法，KMP算法。下面的改進算法就是吸取KMP算法的思想。子串遇到數字時和遇到相同的字母時，可以省去一些計算。

            char* max_unqi_sub(char* src)
            {
                char            * ret = 0;
                            int start = -1;    /*是否確定了子串的起始位置*/
                            int maxlen = 0;
                            int i=0, t=0;

                            for (i=0; src[i]!=0; i++)
                {
                                /* 是否為數字 */
                                if (src[i] >= '0' && src[i] <= '9')
                    {
                                    if (start != -1) /*子串的結束位置*/
                        {
                                        if (i-start > maxlen)
                            {
                                maxlen             = i-start;
                                ret             = src+start;
                            }
                            start             = -1;    
                        }
                        continue;    
                    }
                                else
                    {
                                    if (start == -1) /*子串起始位置*/
                            start             = i;
                                    for (t=start; t<i; t++)
                        {
                                        if (src[i] == src[t]) /*子串的結束位置*/
                            {    
                                            if (i-start > maxlen)
                                {
                                    maxlen             = i-start;
                                    ret             = src+start;
                                }
                                start             = t+1;    /*重新確定起始位置*/
                                break;
                            }
                        }
                    }
                }
                            if (i-start > maxlen)
                {
                    maxlen             = i-start;
                    ret             = src+start;
                }
                
                return ret;
            }
            
算法的復雜度：最差Ｏ(n^2)，當字符串就是非重復子串。最好O(n)，當字符串是數字字符串或者一個元素重復的字符串

            題二：一個自然數可以分解為若干個自然數相乘，求出每種分解自然數之和最少的一個。 如12=2*2*3，和為7=2+2+3
            分析：如果把用窮舉法把所有可能的組合計算出來，那無疑是復雜的。 假設a=b*c。其中b，c>=2。則a>=2*max{b,c}>=a+b。由此可見a因數分解后的和比a小。顯然a的完全因數分解之后的和最小。問題就變成了自然數完全因數分解求和。
            

            #include <math.h>
            unsigned             int minsum(unsigned int n)
            {
                unsigned             int sum = 0;
                unsigned             int div_idx = 2;
                unsigned             int sqrt_n=sqrt(n);
                
                            while (1)
                {
                                if (div_idx > sqrt_n)
                        break;
                                if (n % div_idx ==0)
                    {
                        sum             += div_idx;
                        n             /= div_idx;
                        sqrt_n             = sqrt(n);
                    }
                                else
                        div_idx            ++;
                }
                return sum            +n;
            }
            

            

		
            
		
            
			posted on 2007-12-25 17:29 lemene 閱讀(654) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



久久免费小视频|
午夜精品久久久久久久|
9999国产精品欧美久久久久久|
国产一久久香蕉国产线看观看|
久久WWW免费人成—看片|
国产一区二区久久久|
99久久精品国内|
亚洲欧洲中文日韩久久AV乱码|
伊人久久大香线蕉av一区|
亚洲精品国产美女久久久|
97超级碰碰碰碰久久久久|
色欲久久久天天天综合网|
精品久久人人爽天天玩人人妻|
无码人妻久久一区二区三区免费丨
|
久久国产乱子伦精品免费午夜|
国产aⅴ激情无码久久|
久久久久国产视频电影|
久久精品国产精品青草app|
久久天天躁狠狠躁夜夜avapp|
AA级片免费看视频久久|
午夜久久久久久禁播电影|
久久精品无码一区二区日韩AV|
国产韩国精品一区二区三区久久|
伊人情人综合成人久久网小说|
亚洲一本综合久久|
99999久久久久久亚洲|
久久综合噜噜激激的五月天|
尹人香蕉久久99天天拍|
久久精品国产精品亚洲人人|
91久久成人免费|
国产一级持黄大片99久久|
国产亚洲精品美女久久久|
无码人妻久久久一区二区三区|
久久丫忘忧草产品|
中文字幕无码久久人妻|
欧美一级久久久久久久大片|
久久人人爽人人爽AV片|
亚洲精品高清一二区久久|
无码精品久久一区二区三区|
一本大道久久东京热无码AV|
欧美日韩精品久久免费|