Announcement

Collapse
No announcement yet.

Có ai chỉ giùm thuật toán bài này với!!

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Có ai chỉ giùm thuật toán bài này với!!

    Phân tích số N thành tổng các thừa số
    nguyên tố. Vd: 10 = 1 + 3^2.

  • #2
    1 không phải là số nguyên tố
    Originally posted by 13520582 View Post
    Phân tích số N thành tổng các thừa số
    nguyên tố. Vd: 10 = 1 + 3^2.
    :funny::brick::beauty::what:

    Comment


    • #3
      Bạn làm rồi quăng code lên mọi người sẽ giúp. Đừng nhờ mà không chiệu suy nghĩ vậy.
      Originally posted by 13520582 View Post
      Phân tích số N thành tổng các thừa số
      nguyên tố. Vd: 10 = 1 + 3^2.
      -Trần Hữu Danh-
      -GameUIT - SE-
      ...Slowly... But Strongly...
      clbgameuit.com F/clbgameuit

      Comment


      • #4
        trk hết là tạo 1 mảng chứa các số nguyên tố nhỏ hơn hoặc bằng n, sau đó kểm tra xem n có chia hết cho từng số trong đó hay không và chia hết bao nhiêu lần , thì số lần đó là số mũ tương ứng với số nguyên tố (là số chia) đó lưu vào 1 mảng số nguyên tố ước và 1 mảng tương ứng chứa số mũ.
        vd : phân tích số n = 10.
        b1 : các số nguyên tố nhỏ hơn 10 : 2,3,5,7 -> a[] = {2,3,5,7}
        b2 : 10 chia hết cho 2 ->b[] = {2}
        (int)n = 10 /2 = 5 , 5 ko chia hết cho 2 -> c[] = {1}
        b3 : 5 ko chia hết cho 2 ,3 . nhưng 5 chia hết cho 5 ->b[] = {2,5}
        (int) n = 5 / 5 = 1 (so sanh dk ->thoat) ->c[] = {1,1}
        => như vây t đc 2 mảng b[], c[] tương ứng là số nguyên tố và số mũ.
        :angry::angry::angry::angry:

        Comment


        • #5
          - Đề bài này không rõ ràng nhé. Thừa số chỉ nói trong tích thôi. Còn tổng thì phải là các số hạng.
          - Nếu phân tích n thành tổng các số nguyên tố vì vd trên phải đổi lại thành 10=3+7=5+5 thì mới đúng nha.
          Bạn có thể search Goldbach's_conjecture để biết thêm.

          Bạn 12520250 trả lời theo bài toán phân tích n thành tích các thừa số nguyên tố mới đúng. Nhưng cũng không cần tạo mảng nguyên tố ban đầu như bạn đâu.
          University of Information Technology
          Cao Văn Nhàn _ CE10520355
          SĐT: 0188 403 4943

          Email: caovannhan2002@gmail.com

          Comment


          • #6
            - bạn có thể làm 1 hàm con để xác định các số nguyên tố từ 1 ==> N.
            - sau đó bạn lấy N trừ đi các số nguyên tố đó mũ 2 nếu ra số âm thì số nguyên tố đó không thỏa. nếu là số dương thì số nguyên tố đó mũ 2 + phần N trừ số nguyên tố đó mũ 2 chính là kết quả cần tìm.

            mình làm thử bạn coi đúng yêu cầu không, có gì sai mọi người sửa giúp .
            Code:
            #include <stdio.h>
            #include <conio.h>
            
            void main()
            {
            	int m, i, s;
            	printf("nhap gia tri m: ");
            	scanf("%d",&m);
            	//kiểm tra các số nguyên tố từ m -1 đến 1
            	for(i = m - 1; i > 0; i--) // cho i chạy ngược để tìm được số mũ cao nhất.
            	{
            		if(IsPrime(i) != 0)
            		{
            			s = m - IsPrime(i)*IsPrime(i);
            			if(s > 0)
            			{
            				printf("Gia tri can tim: %d = %d + %d*%d",m,s,IsPrime(i),IsPrime(i)); // in kết quả ra màn hình
            				break;
            			}
            		}
            	}
            	getch();
            }
            
            int IsPrime(int n)
            {
            	int i;
            	//nếu là 1,2,3 thì nó là số nguyên tố trả về chính nó.
            	if(n <= 3 && n > 0)
            	{
            		return n;
            	}
            	else
            	{
            		//kiểm tra xem n có phải số nguyên tố không
            		for( i = 2; i*i < n;i++)
            		{
            			if(n % i == 0)
            			{
            				return 0;
            			}
            			else
            			{
            				return n;
            			}
            		} 
            	}
            }
            Attached Files
            Last edited by 13520844; 02-11-2013, 15:05.

            Comment


            • #7
              Originally posted by 13520844 View Post
              - bạn có thể làm 1 hàm con để xác định các số nguyên tố từ 1 ==> N.
              - sau đó bạn lấy N trừ đi các số nguyên tố đó mũ 2 nếu ra số âm thì số nguyên tố đó không thỏa. nếu là số dương thì số nguyên tố đó mũ 2 + phần N trừ số nguyên tố đó mũ 2 chính là kết quả cần tìm.

              mình làm thử bạn coi đúng yêu cầu không, có gì sai mọi người sửa giúp .
              Code:
              #include <stdio.h>
              #include <conio.h>
              
              void main()
              {
              	int m, i, s;
              	printf("nhap gia tri m: ");
              	scanf("%d",&m);
              	//kiểm tra các số nguyên tố từ m -1 đến 1
              	for(i = m - 1; i > 0; i--) // cho i chạy ngược để tìm được số mũ cao nhất.
              	{
              		if(IsPrime(i) != 0)
              		{
              			s = m - IsPrime(i)*IsPrime(i);
              			if(s > 0)
              			{
              				printf("Gia tri can tim: %d = %d + %d*%d",m,s,IsPrime(i),IsPrime(i)); // in kết quả ra màn hình
              				break;
              			}
              		}
              	}
              	getch();
              }
              
              int IsPrime(int n)
              {
              	int i;
              	//nếu là 1,2,3 thì nó là số nguyên tố trả về chính nó.
              	if(n <= 3 && n > 0)
              	{
              		return n;
              	}
              	else
              	{
              		//kiểm tra xem n có phải số nguyên tố không
              		for( i = 2; i*i < n;i++)
              		{
              			if(n % i == 0)
              			{
              				return 0;
              			}
              			else
              			{
              				return n;
              			}
              		} 
              	}
              }
              Như anh đã nói ở trên là đề không rõ ràng ==> thuật toán của em cũng sai theo. Nhưng có vài điều cần lưu ý.
              Lưu ý định nghĩa số nguyên tố: Số nguyên tố là số tự nhiên lớn hơn 1 chỉ chia hết cho 1 và chính nó.
              Đối với code của em, cơ bản là hàm xác định nguyên tố của em đã bị sai. Ví dụ em hãy thử test với số 9 có phải là nguyên tố không.
              Trong chương trình của em thử cho input là 18, 81 hoặc 1 số lớn hơn như 10010897 em sẽ thấy sai. (có 2 vấn đề là hàm xác định nguyên tố không đúng và chưa xử lý tràn số).
              University of Information Technology
              Cao Văn Nhàn _ CE10520355
              SĐT: 0188 403 4943

              Email: caovannhan2002@gmail.com

              Comment


              • #8
                Originally posted by 13520582 View Post
                Phân tích số N thành tổng các thừa số
                nguyên tố. Vd: 10 = 1 + 3^2.
                Bài này trước hết bạn tạo 1 mảng tạm để lưu các số nguyên tố.
                Tiếp theo bạn dùng thuật toán sau để phân tích số nguyên tố. Dùng vòng for để kiểm tra thôi, đơn giản .
                Code:
                int A[100]; // mang luu so nguyen to
                int i,j=0;
                    for(i = 2; i <=n; i ++)
                	{
                        if(n%i==0)
                		{
                			A[j]=i;
                                        j++;
                			n=n-i;
                			if(n%2==0)
                			{
                				i=1;
                			}
                			else
                				i=2;
                		}
                    }
                Sau khi đã lưu các số vào mảng A. Bạn chỉ cần xuất A ra, thêm "mắm muối" vào cho nó đẹp nữa là ok.

                P/s: Code trên làm gấp nên chưa chuyển thành hàm đc. Bạn tự chuyển nhé ! Chúc em thành công !!!:happy:

                Comment

                LHQC

                Collapse
                Working...
                X