诺西的题，跪求大家帮忙看看，全英文的一道编程题，多谢，通宵

诺西的题，跪求大家帮忙看看，全英文的一道编程题，谢谢，通宵求助
Given a head pointer pointing to a linked list, please write a function that sort the list in increasing order.

Typedef struct S_Node

{

int            data;

struct S_Node  *next;

}Node;

Node*sort_link_list_increasing_order(Node *header);

Ugly numbers are numbers whose only prime（质因数） factors are 2,3or 5.The sequence 1,2,3,4,5,6,8,9,10,12,15,…shows the first 11ugly numbers. By convention,1 is included.

Write a time efficient program to find and print the 1500’th（打印第1500个数） ugly number

[解决办法]

Node*sort_link_list_increasing_order(Node *header);
 {
   Node* p = header;
   int nCount = 0; 
   int num =1;
   int temp =num; 
   while(1) {    
     if(1 == temp){
        p = p->next;p->data = num;
        nCount ++;num++;temp=num;continue;    }   
     if(nCount == 1500){         
        cout<<"finish”;return header;    } 
     if(0 == temp%2){        
        temp = temp >>1;continue;    }    
     if(0 == temp%3){        
       temp =temp/3;continue;    }    
     if(0 == temp%5){        
       temp=temp/5;continue;    }    
     num ++; 
     temp =num;
  }
 } 

[解决办法]
根据题意可以看出所有的数都满足这样一个条件，即可以分解成在它之间的两个数(已经得到的）的乘积。比如8 = 2* 4， 9 = 3*3。
假设已经得到前n个数，设序列为S, 那么Sn+1必然是前n个数中的两个数的乘积，该数是所有可能的乘积中最小的且大于第n个数。
感觉说得不清楚，试试用数学一点的表达： Sn+1 = min(a*b) 且a*b > Sn，其中a,b属于S。
这样问题就转化为一个找满足条件的乘积问题：

low = 1;  high = n - 1;下标从0开始
prod = S[low] * S[high];
while(low <= high){
    if(S[low]*S[high] <= S[n-1]){
        ++low;
    }else{
        if(S[low]*S[high] <　prod){
             prod = S[low]*S[high];
        }
        --high;
    }
}
return prod;

------解决方案--------------------

Ugly numbers 是指 其质数因子只能为2，3，或5的数。

你要打印出第1500个ugly number

查看更多 下一篇