Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Kiểm tra N có phải số hạng 3k hay không

  1. #1
    Ngày gia nhập
    11 2011
    Bài viết
    0

    Mặc định Kiểm tra N có phải số hạng 3k hay không

    Các bạn xem dùm code mình sai chỗ nào mình tìm hoài mà không biết sai chỗ nào
    Đề: Kiểm tra N có phải số hạng 3^k (k là số nguyên duơng) hay không
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #include<math.h>
    4. void main()
    5. {
    6.     double n,a,k,m,b;
    7.     int dem=0;
    8.     unsigned int i;
    9.     do
    10.     {
    11.         printf("Hay nhap so nguyen N khong am1: ");
    12.         scanf("%d",&n);
    13.     }while(n<=0);
    14.     do
    15.     {
    16.         if (n==3)
    17.             printf("Do la so 3k");
    18.         else
    19.         {
    20.         b=log(n);
    21.         m=log(3);
    22.         k=b/m;
    23.         a=(int)pow(3,k);
    24.         if (a==n)
    25.             dem=1;
    26.         else
    27.             dem=0;
    28.         }
    29.     }while(n>=2);
    30.     if (dem==1)
    31.         printf("Do la so 3k");
    32.     if (dem==0)
    33.         printf("Do khong la so 3k");
    34.     getch();
    35. }

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Đây chỉ là việc kiểm tra đơn thuần = 1 biểu thức toán học và sẽ cho ra kết quả "ngay từ lần thử đầu tiên"
    Ko việc gì phải đưa vào vòng lặp.

    Mà cái vòng lặp của bạn nhìn sơ qua là thấy nó lặp vô tận rồi đấy
    Um Mani Padme Hum...!!

  3. #3
    Ngày gia nhập
    11 2011
    Bài viết
    0

    bài này bắt buộc phải dùng vòng lặp do..while hoặc while mà bạn

  4. #4
    Ngày gia nhập
    11 2011
    Bài viết
    4

    - Bạn có thể dùng code sau đây
    long n;
    long TEMP = 1;

    //Nhap vao so n
    //----

    if(n < 0)
    {
    printf("n khong hop le");
    }

    //Kiem tra 3k
    while(TEMP < n)
    {
    TEMP *= 3;
    }

    if(TEMP == n)
    printf("n la so 3k");
    else
    printf("n khong la so 3k");

    - Mình thầy code của bạn gặp vấn để rồi đó: vòng lặp của bạn sao không có điều kiện thoát vậy. Điều này dẫn đến việc vòng lặp sẽ vô hạn.
    Mong điều này có thể giúp bạn

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Trích dẫn Nguyên bản được gửi bởi csfire Xem bài viết
    bài này bắt buộc phải dùng vòng lặp do..while hoặc while mà bạn
    Bạn suy nghĩ rồi thấy là "bắt buộc phải dùng vòng lặp" hay là đề yêu cầu là "bắt buộc phải dùng vòng lặp " ??? . Đề đâu có bắt đâu ??

    Mình thấy với tư tưởng của bạn thế là làm theo cách hay, tức là tính toán toán học xong đưa kết quả.

    Chứ do với chả while gì ở đây nữa?
    Mà bạn có do while thì trong bài của bạn while vẫn ko viết đúng, vì vòng lặp chạy mãi ra cả vũ trụ
    Um Mani Padme Hum...!!

  6. #6
    Ngày gia nhập
    10 2011
    Bài viết
    46

    Mặc định Kiểm tra N có phải số hạng 3k hay không

    Cách đơn giản nhất,
    C++ Code:
    1. #include <stdio.h>
    2.  
    3. bool is_power_of_3(int n) {
    4.     while((n % 3) == 0)
    5.         n /= 3;
    6.     return (n == 1);
    7. }
    8.  
    9. int main() {
    10.     printf("%d\n", is_power_of_3(9));
    11.     printf("%d\n", is_power_of_3(12));
    12. }
    Dùng toán học thì bạn có thể dùng công thức log(n)/log(3). Bài này còn rất nhiều cách hay, tuy vậy mình nghĩ đưa nó ra cũng chỉ làm bạn rối hơn mà thôi. Tập trung để hiểu cách đầu tiên là đủ, vì nó là đặc trưng của giải thuật. Khi bạn học đến Turing Machine, bạn vẫn có thể áp dụng nó, trong khi nếu dùng công thức thì sẽ khó khăn hơn rất nhiều.

  7. #7
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Nếu xem phép log có độ phức tạp 1 thì cách dùng công thức toán học nhanh hơn chứ sao lại ưu tiên "đặc trưng của giải thuật" .
    Mình thấy vô cùng đơn giản dễ hiểu chứ có rối gì đâu ?
    k = log(n)/log(3) .
    if k==int(k)
    say YES
    else
    say NO
    Um Mani Padme Hum...!!

  8. #8
    Ngày gia nhập
    10 2011
    Bài viết
    46

    Hàm log không phải O(1), nó sử dụng rất nhiều giải thuật cho approximation. Mình không phủ nhận trong bài này dùng log() là nhanh hơn, tất nhiên các người viết giải thuật đã dùng rất nhiều thủ thuật để tối ưu nó rồi. Tuy vậy, bản chất của nó vẫn dựa trên Taylor Polynomial.
    Cách kia tuy không tối ưu, nhưng đơn giản và hợp với bạn mới học kia hơn. Đây là hàm log.c
    C++ Code:
    1.  
    2. /* @(#)e_log.c 1.3 95/01/18 */
    3. /*
    4.  * ====================================================
    5.  * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
    6.  *
    7.  * Developed at SunSoft, a Sun Microsystems, Inc. business.
    8.  * Permission to use, copy, modify, and distribute this
    9.  * software is freely granted, provided that this notice
    10.  * is preserved.
    11.  * ====================================================
    12.  */
    13.  
    14. /* __ieee754_log(x)
    15.  * Return the logrithm of x
    16.  *
    17.  * Method :                  
    18.  *   1. Argument Reduction: find k and f such that
    19.  *          x = 2^k * (1+f),
    20.  *     where  sqrt(2)/2 < 1+f < sqrt(2) .
    21.  *
    22.  *   2. Approximation of log(1+f).
    23.  *  Let s = f/(2+f) ; based on log(1+f) = log(1+s) - log(1-s)
    24.  *       = 2s + 2/3 s**3 + 2/5 s**5 + .....,
    25.  *           = 2s + s*R
    26.  *      We use a special Reme algorithm on [0,0.1716] to generate
    27.  *  a polynomial of degree 14 to approximate R The maximum error
    28.  *  of this polynomial approximation is bounded by 2**-58.45. In
    29.  *  other words,
    30.  *              2      4      6      8      10      12      14
    31.  *      R(z) ~ Lg1*s +Lg2*s +Lg3*s +Lg4*s +Lg5*s  +Lg6*s  +Lg7*s
    32.  *      (the values of Lg1 to Lg7 are listed in the program)
    33.  *  and
    34.  *      |      2          14          |     -58.45
    35.  *      | Lg1*s +...+Lg7*s    -  R(z) | <= 2
    36.  *      |                             |
    37.  *  Note that 2s = f - s*f = f - hfsq + s*hfsq, where hfsq = f*f/2.
    38.  *  In order to guarantee error in log below 1ulp, we compute log
    39.  *  by
    40.  *      log(1+f) = f - s*(f - R)    (if f is not too large)
    41.  *      log(1+f) = f - (hfsq - s*(hfsq+R)). (better accuracy)
    42.  * 
    43.  *  3. Finally,  log(x) = k*ln2 + log(1+f).  
    44.  *              = k*ln2_hi+(f-(hfsq-(s*(hfsq+R)+k*ln2_lo)))
    45.  *     Here ln2 is split into two floating point number:
    46.  *          ln2_hi + ln2_lo,
    47.  *     where n*ln2_hi is always exact for |n| < 2000.
    48.  *
    49.  * Special cases:
    50.  *  log(x) is NaN with signal if x < 0 (including -INF) ;
    51.  *  log(+INF) is +INF; log(0) is -INF with signal;
    52.  *  log(NaN) is that NaN with no signal.
    53.  *
    54.  * Accuracy:
    55.  *  according to an error analysis, the error is always less than
    56.  *  1 ulp (unit in the last place).
    57.  *
    58.  * Constants:
    59.  * The hexadecimal values are the intended ones for the following
    60.  * constants. The decimal values may be used, provided that the
    61.  * compiler will convert from decimal to binary accurately enough
    62.  * to produce the hexadecimal values shown.
    63.  */
    64.  
    65. #include "fdlibm.h"
    66.  
    67. #ifdef __STDC__
    68. static const double
    69. #else
    70. static double
    71. #endif
    72. ln2_hi  =  6.93147180369123816490e-01/* 3fe62e42 fee00000 */
    73. ln2_lo  =  1.90821492927058770002e-10/* 3dea39ef 35793c76 */
    74. two54   =  1.80143985094819840000e+16,  /* 43500000 00000000 */
    75. Lg1 = 6.666666666666735130e-01,  /* 3FE55555 55555593 */
    76. Lg2 = 3.999999999940941908e-01,  /* 3FD99999 9997FA04 */
    77. Lg3 = 2.857142874366239149e-01,  /* 3FD24924 94229359 */
    78. Lg4 = 2.222219843214978396e-01,  /* 3FCC71C5 1D8E78AF */
    79. Lg5 = 1.818357216161805012e-01,  /* 3FC74664 96CB03DE */
    80. Lg6 = 1.531383769920937332e-01,  /* 3FC39A09 D078C69F */
    81. Lg7 = 1.479819860511658591e-01;  /* 3FC2F112 DF3E5244 */
    82.  
    83. static double zero   =  0.0;
    84.  
    85. #ifdef __STDC__
    86.     double __ieee754_log(double x)
    87. #else
    88.     double __ieee754_log(x)
    89.     double x;
    90. #endif
    91. {
    92.     double hfsq,f,s,z,R,w,t1,t2,dk;
    93.     int k,hx,i,j;
    94.     unsigned lx;
    95.  
    96.     hx = __HI(x);       /* high word of x */
    97.     lx = __LO(x);       /* low  word of x */
    98.  
    99.     k=0;
    100.     if (hx < 0x00100000) {          /* x < 2**-1022  */
    101.         if (((hx&0x7fffffff)|lx)==0)
    102.         return -two54/zero;     /* log(+-0)=-inf */
    103.         if (hx<0) return (x-x)/zero;    /* log(-#) = NaN */
    104.         k -= 54; x *= two54; /* subnormal number, scale up x */
    105.         hx = __HI(x);       /* high word of x */
    106.     }
    107.     if (hx >= 0x7ff00000) return x+x;
    108.     k += (hx>>20)-1023;
    109.     hx &= 0x000fffff;
    110.     i = (hx+0x95f64)&0x100000;
    111.     __HI(x) = hx|(i^0x3ff00000);    /* normalize x or x/2 */
    112.     k += (i>>20);
    113.     f = x-1.0;
    114.     if((0x000fffff&(2+hx))<3) { /* |f| < 2**-20 */
    115.         if(f==zero) if(k==0) return zero;  else {dk=(double)k;
    116.                  return dk*ln2_hi+dk*ln2_lo;}
    117.         R = f*f*(0.5-0.33333333333333333*f);
    118.         if(k==0) return f-R; else {dk=(double)k;
    119.                  return dk*ln2_hi-((R-dk*ln2_lo)-f);}
    120.     }
    121.     s = f/(2.0+f);
    122.     dk = (double)k;
    123.     z = s*s;
    124.     i = hx-0x6147a;
    125.     w = z*z;
    126.     j = 0x6b851-hx;
    127.     t1= w*(Lg2+w*(Lg4+w*Lg6));
    128.     t2= z*(Lg1+w*(Lg3+w*(Lg5+w*Lg7)));
    129.     i |= j;
    130.     R = t2+t1;
    131.     if(i>0) {
    132.         hfsq=0.5*f*f;
    133.         if(k==0) return f-(hfsq-s*(hfsq+R)); else
    134.              return dk*ln2_hi-((hfsq-(s*(hfsq+R)+dk*ln2_lo))-f);
    135.     } else {
    136.         if(k==0) return f-s*(f-R); else
    137.              return dk*ln2_hi-((s*(f-R)-dk*ln2_lo)-f);
    138.     }
    139. }
    Nó không đơn giản như bạn đã nghĩ.

  9. #9
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Nếu xem phép log có độ phức tạp 1 thì cách dùng công thức toán học nhanh hơn chứ sao lại ưu tiên "đặc trưng của giải thuật" .
    Mình thấy vô cùng đơn giản dễ hiểu chứ có rối gì đâu ?
    k = log(n)/log(3) .
    if k==int(k)
    say YES
    else
    say NO
    Nếu phần nguyên của k rất lớn và phần thập phân của k rất nhỏ thì k sẽ bị vượt giới hạn độ chính xác.
    Lúc đó, con toán k==int(k) có còn tin cậy được không ta? Lâu ngày quên mất nó ra sao rôi. Bữa nào rảnh phải nghiên cứu lại mới được.

  10. #10
    Ngày gia nhập
    10 2011
    Bài viết
    552

    @ Halen & VTS :
    Yes ! Thanks. Mình cũng đã nhìn nhận lại vấn đề là thực hiện phép log trên giấy tờ thì thật là "đơn giản" nhưng đi sâu sát vào bản chất nó tạo thành từ quá trình thực hiện chuỗi Taylor trên vi xử lý thì thật ko đơn giản chút nào.
    Thêm vào đó phép toán về số thực luôn đeo đuổi bên cạnh nó một sai số nhất định
    Alright! Sẽ ko lạm dụng "toán học" vào lập trình nữa .

    Bữa giờ cứ mụ mị là Phép gán và các hàm toán học cơ bản trong C , ta cứ mặc định nó là O(1). Nhưng đôi khi tìm hiểu vào thì thực sự nó ko phải vậy.
    Một lần nữa, cảm ơn 2 tiền bối
    Um Mani Padme Hum...!!

Các đề tài tương tự

  1. Trả lời: 6
    Bài viết cuối: 31-07-2013, 07:51 PM
  2. Mỹ phẩm Thu Huyền: Bộ mỹ phẩm trị nám, tàn nhang Bride Korea - call 0906.260.160
    Gửi bởi kimkim8910 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 12-03-2012, 10:49 PM
  3. phần merge module bị thiếu crystal report phải làm thế nào ?
    Gửi bởi manhluc88 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 06-01-2011, 01:11 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn