作者 主題: (不用迴圈)求完全數  (閱讀 9896 次)

0 會員 與 1 訪客 正在閱讀本文。

shang1112

  • 可愛的小學生
  • *
  • 文章數: 5
    • 檢視個人資料
(不用迴圈)求完全數
« 於: 2010-12-06 23:35 »
題目:完全數。一個數等於它所有的因數和,這種數我們叫它完全數﹝不包括它本身﹞。像:6=1+2+3,28=1+2+4+7+14。請求出第三、第四以及第五個完全數。

我用迴圈的方式寫了一個,本來都要交給老師了,但是執行之後發現只能求出第三及第四個完全數,最後一個等很久就是跑不出來,想說是不是該用計算完全數的公式?或者有什麼相關的函數?
(公式是(2的n次方-1)*2的n次方/2    (條件:n為自然數且2的n次方-1為質數);但我也沒用C語言表示過n次方這樣的東西欸)

這是我用迴圈寫的程式,總之最後一個就是跑不出來啊。
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    int a,b,sum=0,num=0;
    for(a=29;a>0;a++)
    {           
        for(b=1;b<a;b++)
        {           
           if(a%b==0) sum+=b;
        }
        if(sum==a)
        {
           printf("%d=",a);
           num+=1;
           for(b=1;b<a;b++)
           {
             if(a%b==0) printf("%d+",b);
           }
           printf("0,\n");
        }
        sum=0;
        if(num==3) a=0;
    }
    system("pause");
    return 0;
}

真的很謝謝願意幫我解決難題的大大啊OUO
謝謝你



TyroneYeh

  • 俺是博士!
  • *****
  • 文章數: 2396
  • 性別: 男
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #1 於: 2010-12-07 08:29 »
沒看問題,看程式的這行 for(a=29;a>0;a++) 是不是有問題?
--
TyroneYeh

Yamaka

  • 俺是博士!
  • *****
  • 文章數: 4913
    • 檢視個人資料
    • http://www.ecmagic.com
回覆: (不用迴圈)求完全數
« 回覆 #2 於: 2010-12-07 08:56 »
題目:完全數。一個數等於它所有的因數和,這種數我們叫它完全數﹝不包括它本身﹞。像:6=1+2+3,28=1+2+4+7+14。請求出第三、第四以及第五個完全數。

我用迴圈的方式寫了一個,本來都要交給老師了,但是執行之後發現只能求出第三及第四個完全數,最後一個等很久就是跑不出來,想說是不是該用計算完全數的公式?或者有什麼相關的函數?
(公式是(2的n次方-1)*2的n次方/2    (條件:n為自然數且2的n次方-1為質數);但我也沒用C語言表示過n次方這樣的東西欸)

這是我用迴圈寫的程式,總之最後一個就是跑不出來啊。
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    int a,b,sum=0,num=0;
    for(a=29;a>0;a++)
    {           
        for(b=1;b<a;b++)
        {           
           if(a%b==0) sum+=b;
        }
        if(sum==a)
        {
           printf("%d=",a);
           num+=1;
           for(b=1;b<a;b++)
           {
             if(a%b==0) printf("%d+",b);
           }
           printf("0,\n");
        }
        sum=0;
        if(num==3) a=0;
    }
    system("pause");
    return 0;
}

2^12 x (2^13 - 1) = 33550336

應該要花不少時間來跑

fillano

  • 鑽研的研究生
  • *****
  • 文章數: 526
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #3 於: 2010-12-07 12:40 »
既然有公式,假設公式是對的,那你解題只需要使用公式就好了阿?

你手算一下就知道,題目是已知n==2及n==3的狀況,所以你需要找的是n>3狀況下的結果,只要找到三個就可以結束。主要的判斷條件也在題目裡,就是某個「是否是質數」的條件阿。

至於不用迴圈?我就不知道了。
Sapere aude! Habe Mut, dich deines eigenen Verstandes zu bedienen! ist also der Wahlspruch der Aufklärung.

bunko

  • 懷疑的國中生
  • **
  • 文章數: 67
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #4 於: 2010-12-07 13:47 »
//      perfect_number.c
//  Perfect Numbers under 10000
#include <stdio.h>

int main(int argc, char **argv)
{
   int a, i, sum;
   printf("This Program will show Perfect Numbers under 10000:\n");
   
   for(a=1; a <= 10000; a++) {
      sum = 0;
      for(i=1; i <= (a / 2) ; i++) {
         if((a % i) == 0) {
            sum += i;
            if( sum == a) {
               printf("perfect number: %4d\n", a);
               break;
            }
         }
      }
   }
   printf("---------------------\n");
   printf("Done!\n");
   return 0;
}


我只會用迴圈來解.......執行結果如下:
This Program will show Perfect Numbers under 10000:
perfect number:    6
perfect number:   24
perfect number:   28
perfect number:  496
perfect number: 2016
perfect number: 8128
perfect number: 8190
---------------------
Done!

補充說明,剛剛看了一下perfect number的定義,我這個程式列出來的沒有符合perfect number的定義.
24 不是2016也不是,8128是.8190也不是.........
===============================
底下是另一個,可以找比較多數字的........但是還是會多找出一些東西

#include <stdio.h>
#include <limits.h>
int main(int argc, char **argv)
{
   int running = 1,count,p;
   unsigned long long a, i, sum;
   printf("This Program can find Perfect Numbers under %llu:\n", ULLONG_MAX );
   printf("How many Pefect Numbers you want to find?");
   scanf("%i", &p);
   a = 0; count=0;
   while(running) {
      a += 2;
      
      if( a >= ULLONG_MAX) {
         running = 0;
      }
      sum = 0;
      for(i=1; i <= (a / 2) ; i++) {
         if((a % i) == 0) {
            sum += i;
            if( sum == a) {
               count++;
               printf("#%d perfect number: %20llu\n",count, a);
               
               if( count == p) {
                  running = 0;
               }
               break;
            }
         }
      }
   }
   printf("---------------------\n");
   printf("Done!\n");
   return 0;
}

-------------------------------------



« 上次編輯: 2010-12-07 15:34 由 bunko »

TyroneYeh

  • 俺是博士!
  • *****
  • 文章數: 2396
  • 性別: 男
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #5 於: 2010-12-07 13:52 »
不用迴圈,有另一種的方法,叫「遞迴」
簡單一點就是 function 裡面呼叫自己,當參數某個值符合的時候就會離開自己
弄不好就是無限迴圈...
--
TyroneYeh

bunko

  • 懷疑的國中生
  • **
  • 文章數: 67
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #6 於: 2010-12-07 17:29 »
另一個用公式算的.

//      perfect3.c
//      
#include <stdio.h>
#include <math.h>
int main(int argc, char **argv)
{
   unsigned long long perf;
   double i;
   
   for(i=2.0; i <= 13.0; i++) {
      perf = (unsigned long long) pow(2.0, (i-1.0)) * (pow(2.0, i) - 1.0);
      printf("it maybe is a perfect number:%llu\n", perf);
   }
   return 0;
}
-------------------------------------------
編譯時要引入math函數庫.
$ gcc -Wall -lm  perfect3.c -o perfect3

$ ./perfect3
it maybe is a perfect number:6
it maybe is a perfect number:28
it maybe is a perfect number:120
it maybe is a perfect number:496
it maybe is a perfect number:2016
it maybe is a perfect number:8128
it maybe is a perfect number:32640
it maybe is a perfect number:130816
it maybe is a perfect number:523776
it maybe is a perfect number:2096128
it maybe is a perfect number:8386560
it maybe is a perfect number:33550336

32640到8386560 都不是, 33550336 才是真正第五個完全數.

參考一下囉~~~ :) 另外上面那個呆呆一直算的程式,只要把一部分程式碼搬動一下,就不會多算一些數字出來了.
« 上次編輯: 2010-12-07 17:31 由 bunko »

bunko

  • 懷疑的國中生
  • **
  • 文章數: 67
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #7 於: 2010-12-07 18:18 »
代碼: (c) [選擇]
//      perfect4.c

#include <stdio.h>
#include <math.h>
int main(int argc, char **argv)
{
unsigned long long pa[12];
unsigned long long sum,i;
double n;
int j=0,count=0;

for(n=2.0; n <= 13.0; n++) {
pa[j++] = (unsigned long long) pow(2.0, (n-1.0)) * (pow(2.0, n) - 1.0);

}

for(j=0; j <= 11; j++) {

printf("it maybe is a perfect number:%llu\n", pa[j]);
}
printf("=================================================\n");
printf("The real perfect numbers:\n");
count = 0;
for(j=0; j <= 11; j++) {
sum = 0;
for(i=1; i <= (pa[j]/2); i++) {
if((pa[j] % i) == 0) {
sum += i;
}
}
if( sum == pa[j]) {

printf("\n#%d perfect number: %20llu\n",++count, pa[j]);
}
}

return 0;
}

----------------------------
編譯時一樣記得把math包含進來.
先用公式計算,然後存到array, 然後取出array內的可能為perfect number的值,再用暴力法驗算,驗算符合後印出來.
可是....還是用迴圈快多了....

$gcc -Wall -lm  perfect4.c -o perfect4
$ ./perfect4
it maybe is a perfect number:6
it maybe is a perfect number:28
it maybe is a perfect number:120
it maybe is a perfect number:496
it maybe is a perfect number:2016
it maybe is a perfect number:8128
it maybe is a perfect number:32640
it maybe is a perfect number:130816
it maybe is a perfect number:523776
it maybe is a perfect number:2096128
it maybe is a perfect number:8386560
it maybe is a perfect number:33550336
=================================================
The real perfect numbers:

#1 perfect number:                    6

#2 perfect number:                   28

#3 perfect number:                  496

#4 perfect number:                 8128

#5 perfect number:             33550336


« 上次編輯: 2010-12-07 18:23 由 bunko »

shang1112

  • 可愛的小學生
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #8 於: 2010-12-08 18:11 »
for(a=29;a>0;a++)這行應該是正確的,因為程式跑得出前兩個數。
跑不出最後一個數的原因應該是因為太大,要跑太久。
我們老師說太久不好。要我們試試別的。

bunko大的第一個回覆我試著改了一下:
  for(a=1; a <= 10000; a++) {
      sum = 0;
      for(i=1; i <= (a / 2) ; i++) {
         if((a % i) == 0) {
            sum += i;
            if( sum == a) {
               printf("perfect number: %4d\n", a);
               break;
            }
         }
      }
   }
for(i=1; i <= (a / 2) ; i++) {
改成for(i=1;i<a;i++)
if((a%i)==0)和if(sum==a)改成並列關係,就可以順利的跑出來了。
不過這好像跟我原本寫的差不多。

我想要跑跑看你給我的第四個回覆,可是跑不出來欸
(我還沒學到函數那邊;不太懂把math包含進來是?)
而且,大大你居然說這比迴圈還慢...這讓我很緊張

噢,總之先謝謝回覆的各位一聲囉。= D
« 上次編輯: 2010-12-08 18:13 由 shang1112 »

bunko

  • 懷疑的國中生
  • **
  • 文章數: 67
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #9 於: 2010-12-08 20:33 »
$gcc -Wall -lm  perfect4.c -o perfect4

這樣編譯......裡面那個 -lm 就是把數學函數包進來.

這個程式可以算出第五個沒問題,但是後面的話......我有留個bug......
你試試看,也可以看看是哪邊有bug.
我都是用迴圈......
那句話我沒表達的很好,造成你誤會了,你就先不管它囉...
這個程式不會跑很久,因為它只有挑一些來算.
« 上次編輯: 2010-12-08 20:36 由 bunko »

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #10 於: 2010-12-15 13:10 »
關於這個問題,老師有沒有一些限制,例如不能使用查表法,查表法應該是最快的了。

bunko

  • 懷疑的國中生
  • **
  • 文章數: 67
    • 檢視個人資料
回覆: (不用迴圈)求完全數
« 回覆 #11 於: 2010-12-15 14:26 »
代碼: (c) [選擇]
// Find Pefect Number and Calculate CPU Time   

#include <stdio.h>
#include <time.h>

unsigned long long mkperf(unsigned int n);
int is_perfect(unsigned long long p);
char* get_time(void);

int main(int argc, char **argv)
{
unsigned int i, count = 0;
unsigned long long perf,last, r;
unsigned long long num[34];
unsigned long long pb[34];
int cheat[8] = {0, 1, 2, 4, 8, 11, 13, 22};
clock_t start, end, shstart, shend;
double cpu_time_used;

last = 1;

for(i=1; i <= 33; i++) {
perf = mkperf(i);
if ( perf >= last) {
// printf("i=%2d perf=%20llu\n", i, perf);
num[i] = perf;
} else {
printf("****over in i=%2d perf=%20llu\n", i, perf);
break;
}
last = perf;
}

for(i=1; i <= 33; i++) {
r = num[i] % 10;
if ( r == 6 || r == 8) {
printf("maybe is a perfect number:%20Lu\n", num[i]);
pb[count++] = num[i];
}
}

printf("Count = %u\n", count);
printf("will check these numbers\n");
for(i=0; i<=5; i++) {
printf("%20Lu\n", pb[cheat[i]]);
}

printf("---- Checking ----\n");
printf("Start at %s\n", get_time());
start = clock();
// Checking Loop [START]
for(i=0; i <= 5; i++) {
shstart = clock();
if( is_perfect(pb[cheat[i]]) ) {
shend = clock();
cpu_time_used = ((double) (shend - shstart)) / CLOCKS_PER_SEC;
printf("%20Lu is perfect number\n", pb[cheat[i]]);
printf("at %s CPU Time Used:%f\n", get_time(), cpu_time_used);
}
}
// Checking Loop [END]
end = clock();
printf("End   at %s\n", get_time());
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("CPU Time Used = %f\n", cpu_time_used);



return 0;
}

unsigned long long mkperf(unsigned int n)
{ //
unsigned long long p=1;
p <<= n;
p--;
p <<= (n-1);
return p;
}


int is_perfect(unsigned long long p)
{
unsigned long long i, sum;
sum = 0;
for(i=1; i <= (p/2); i++) {
if((p % i) == 0) {
sum += i;
}
}
if( sum == p) {
return 1;
} else {
return 0;
}
}

char* get_time(void)
{
time_t timeval;

(void)time(&timeval);
return ctime(&timeval);
}

--------------------------------------------------
執行結果:
maybe is a perfect number:                   6
maybe is a perfect number:                  28
maybe is a perfect number:                 496
maybe is a perfect number:                2016
maybe is a perfect number:                8128
maybe is a perfect number:              130816
maybe is a perfect number:              523776
maybe is a perfect number:             2096128
maybe is a perfect number:            33550336
maybe is a perfect number:           134209536
maybe is a perfect number:           536854528
maybe is a perfect number:          8589869056
maybe is a perfect number:         34359607296
maybe is a perfect number:        137438691328
maybe is a perfect number:       2199022206976
maybe is a perfect number:       8796090925056
maybe is a perfect number:      35184367894528
maybe is a perfect number:     562949936644096
maybe is a perfect number:    2251799780130816
maybe is a perfect number:    9007199187632128
maybe is a perfect number:  144115187807420416
maybe is a perfect number:  576460751766552576
maybe is a perfect number: 2305843008139952128
Count = 23
will check these numbers
                   6
                  28
                 496
                8128
            33550336
          8589869056
---- Checking ----
Start at Wed Dec 15 14:17:48 2010

                   6 is perfect number
at Wed Dec 15 14:17:48 2010
 CPU Time Used:0.000000
                  28 is perfect number
at Wed Dec 15 14:17:48 2010
 CPU Time Used:0.000000
                 496 is perfect number
at Wed Dec 15 14:17:48 2010
 CPU Time Used:0.000000
                8128 is perfect number
at Wed Dec 15 14:17:48 2010
 CPU Time Used:0.000000
            33550336 is perfect number
at Wed Dec 15 14:17:49 2010
 CPU Time Used:0.420000
          8589869056 is perfect number
at Wed Dec 15 14:19:52 2010
 CPU Time Used:121.840000
End   at Wed Dec 15 14:19:52 2010

CPU Time Used = 122.260000

受限於系統的CPU/與unsigned long long的大小,所以能運算的有限制,而且後面的要花很多時間.
故計算到8589869056.第53行可以改一下i的上限,就會多驗算了.