• <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麻豆小说|
精品熟女少妇a∨免费久久|
一级做a爰片久久毛片16|
亚洲国产精品无码久久久久久曰|
久久夜色精品国产欧美乱|
91精品国产色综久久|
伊人久久大香线蕉亚洲五月天|
久久精品成人国产午夜|
久久人人爽人人爽人人片AV麻烦|
久久久久久久久无码精品亚洲日韩
|
99久久综合国产精品免费|
72种姿势欧美久久久久大黄蕉|
久久久人妻精品无码一区|
人妻精品久久久久中文字幕69|
亚洲AV日韩精品久久久久久久|
久久国产亚洲精品|
中文无码久久精品|
亚洲成人精品久久|
97久久国产露脸精品国产|
国产女人aaa级久久久级|
国产精品一久久香蕉国产线看观看|
久久人人爽人人澡人人高潮AV
|
久久天天躁狠狠躁夜夜躁2O2O
|
国产精品一区二区久久|
国产精品99久久久久久宅男小说|
国产激情久久久久影院老熟女|
久久综合九色综合网站|
久久人人爽人人爽人人爽|
久久中文精品无码中文字幕|
一本色道久久88加勒比—综合|
久久国产色AV免费看|
激情伊人五月天久久综合|
久久人人爽人人爽人人片AV不
|
久久亚洲AV无码精品色午夜麻豆|
久久天天躁狠狠躁夜夜2020|
精品久久久久中文字|
久久亚洲精品无码播放|
久久久久无码专区亚洲av|