yxCoding

I am a coder

分解整数

yxjoey posted @ 2008年5月28日 07:13 in C语言 with tags c 程序 , 2533 阅读

今天在网上闲看,发现最近正在举行2008年百度之星大赛,于是看看了历年试题,挺有意思的
2005年有一道题目是这样的

题目描述:一个正整数有可能可以被表示为 n(n>=2) 个连续正整数之和,如:

15=1+2+3+4+5
15=4+5+6
15=7+8

请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。

输入数据:一个正整数,以命令行参数的形式提供给程序。

最近正好在找实习,肯定会遇到当场写代码的,于是写下这个程序算个练习

  1. #include <stdio.h>
  2. void decomposed_sum(int num);
  3. void decomposed_product(int num);
  4.  
  5. int main(int argc, char *argv[]){
  6.   int num =  atoi(argv[1]);
  7.   printf("========= sum decompsition ========\n");
  8.   decomposed_sum(num);
  9.   printf("========= product decompsition ========\n");
  10.   decomposed_product(num);
  11. }
  12. /* To decompse as sumation is almost the same as to decompse as production
  13. * Assume the number can be decompsed as n numbers starting from a
  14. *    num = (2a+n-1)*n/2
  15. * => 2num = (2a+n-1)*n
  16. *
  17. */
  18. void decomposed_sum(int num){
  19.   num = 2*num;
  20.   int n;
  21.   int start;
  22.   int tmp;
  23.   int k;
  24.   for(n=2; n*n < num; n++){
  25.     if(num % n == 0){
  26.       tmp = num/n;
  27.       if(n%2||tmp%2){
  28.         start = (tmp-n+1)/2;
  29.         printf("%d = %d", num/2, start);
  30.         for(k=1; k<n; k++)
  31.           printf("+%d", start+k);
  32.         printf("\n");
  33.       }
  34.     }
  35.   }
  36. }
  37.  
  38. void decomposed_product(int num){
  39.   if(num<2)
  40.     return;
  41.   int k=2;
  42.   printf("%d = ", num);
  43.   while(k*k<=num){
  44.     while(num%k == 0){
  45.       printf("%d  ", k);
  46.       num /= k;
  47.     }
  48.     k++;
  49.   }
  50.   if(num>1)
  51.     printf("%d", num);
  52.   printf("\n");
  53. }
  54.  

 

原来没写过分解质因数,顺便也写了一边

yxjoey@yxjoey-laptop:~/Sandbox$ ./decompose 300
========= sum decompsition ========
300 = 99+100+101
300 = 58+59+60+61+62
300 = 34+35+36+37+38+39+40+41
300 = 13+14+15+16+17+18+19+20+21+22+23+24+25+26+27
300 = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24
========= product decompsition ========
300 = 2  2  3  5  5 
 

 

Avatar_small
zhlmmc 说:
2008年6月02日 08:51

if(num % n == 0)

什么意思?

num 如果是 15的话, n可以是2,但是15 % 2 = 1啊

Head_small
yxjoey 说:
2008年6月02日 20:50

因为num一开始(19行)已经被我乘以2了, 看我注释里面的那个推导公式,2num要能够被n整除才行


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter