• <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 閱讀(652) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



武侠古典久久婷婷狼人伊人|
国产午夜精品久久久久九九电影|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
久久久无码一区二区三区|
精品久久人妻av中文字幕|
精品国产综合区久久久久久|
久久精品国产亚洲AV影院|
美女写真久久影院|
久久人妻无码中文字幕|
国产高潮国产高潮久久久|
久久久久亚洲爆乳少妇无|
久久超乳爆乳中文字幕|
日韩一区二区三区视频久久|
www.久久精品|
色综合久久无码中文字幕|
久久人妻少妇嫩草AV蜜桃|
国产一区二区三区久久精品|
久久强奷乱码老熟女网站|
久久精品中文字幕一区|
久久天堂电影网|
久久66热人妻偷产精品9|
波多野结衣久久一区二区|
99久久精品免费国产大片|
久久国产乱子伦免费精品|
伊人久久大香线蕉综合Av
|
久久精品国产亚洲αv忘忧草|
国产精品九九久久精品女同亚洲欧美日韩综合区
|
女同久久|
亚洲国产精品久久久久久|
午夜精品久久久久久久久|
伊人久久精品影院|
久久中文字幕视频、最近更新|
香蕉久久夜色精品国产小说|
国产精品视频久久久|
av无码久久久久久不卡网站|
久久国产色AV免费看|
精品久久久久久无码中文字幕一区
|
中文字幕久久欲求不满|
欧美777精品久久久久网|
久久精品这里热有精品|
91精品国产91久久久久久|