Bài tập nghiên cứu lần 1

Bài toán 1:

Cho số tự nhiên A. Hãy tìm số tự nhiên  N nhỏ nhất sao cho {N^N} chia hết cho A  . Trong đó  có giá trị trong khoảng  [1, {10^9}].

Ý tưởng 

Số b chia hết cho a khi và chỉ khi lũy thừa các số nguyên tố trong phân tích của b không nhỏ hơn trong phân tích của a. Như vậy ta để tìm số N điều đầu tiên cần làm là phân tích A  ra số nguyên tố:

A = a_1^{k_2}a_2^{k_2}...a_n^{k_n}

Chắc chắn một điều  số  ta cần tìm là bội của các số a_1, ta lấy tích N_0 = a_1a_2...a_n,  và sao sánh N_0 với lũy thừa của các ước  trong  phân tích của A.

  • Nếu  N_0 \ge max_{i=1..n}(k_i) ta chọn N = N_0.
  • Ngược lại, ta nhân N_0   với  các số tự nhiên  tăng dần (2, 3, …) cho đến khi  N_0 thỏa mãn tính chất trên. Đến đây nảy sinh vấn đề nếu thừa số nhân vào  cũng là ước hay chia hết cho ước của A thì sao?  Khi đó ta phải tăng lũy thừa của  trong  lên trong quá trình kiểm tra.
    vis du: A = 8 = 2^3 \Rightarrow N_0 = 2\ do\ N_0 < max_{i=1..n}(k_i) = 2 \Rightarrow N = N_0\times2 = 4 . Kiểm tra thấy N = 4 thỏa. Kết thúc quá trình.

Code

//BT NMCNTT - Tim so n nho nhat thoa n^n chia het cho so A cho truoc
#include<stdio.h>
#include<math.h>
//Ham kiem tra so nguyen to
int kt_nguyento(int n)
{
    int i, dem=0;
    for (i=2;i<=sqrt(n);i++)
    {
        if (n%i == 0) dem++;        
    };
    if (dem==0) return 1;
    else return 0;    
};
//Ham phan tich ra thua so nguyen to
void uoc_so(unsigned int A, int *uoc, int *so_mu, int &temp1)
{
    unsigned int a, temp2, j;
    temp1=0;
    a=A;
    for (j=2;a>1;j++)
    {
        if (kt_nguyento(j))
             if ((a%j)==0)
            {
                temp1++;
                uoc[temp1]=j;
                temp2=0;
                while (a%j==0)
                {
                    a=a/j;
                    temp2++;
                };
                so_mu[temp1]=temp2;
            };
    };
};
//Ham kiem tra su trung lap uoc nguyen to
void kt_uoc(int m, int temp1, int *uoc, int *so_mu_2)
{    
    int i;
    for (i=1; i<=temp1; i++ )
    {
        while ((m%uoc[i])==0)
        {
            so_mu_2[i]=so_mu_2[i]+1;
            m =(m/(uoc[i]));
        };
    };
};
//Ham kiem tra n thoa yeu cau chua
int kt_yeucau(unsigned int n, int temp1, int *so_mu, int *so_mu_2)
{
    int i;
    for (i=1; i<=temp1; i++ )
    {
        if ((n*so_mu_2[i])<so_mu[i])
        {
            break;
        };
    };
    if (i== (temp1+1)) return 0;
    else return 1;
};
//Chuong trinh chinh
int main()
{
    unsigned int A, n;
    int m, uoc[100], so_mu[100], so_mu_2[100], temp1, k;
    char thu;
    do
    {
        printf("A = ");
        scanf("%u",&A);    
        uoc_so(A, &uoc[0], &so_mu[0], temp1);
        n=1;
        printf("%u = ",A);
        for (k=1;k<=temp1;k++)
        {
            printf("(%d^%d)",uoc[k],so_mu[k]);
            n*=uoc[k];
            so_mu_2[k]=1;
        }; //In ra phan ticb nguyen to cua so A
        m=1;
        while (kt_yeucau((n*m), temp1, &so_mu[0], &so_mu_2[0]))
        {        
            m++;
            for (k=1; k<=temp1; k++)
            {
                so_mu_2[k]=1;
            };
            kt_uoc(m, temp1, &uoc[0], &so_mu_2[0]);                
        };
        printf("\nSo nho nhat thoa yeu cau la %u\n",(n*m));
        printf("Again? (Press y to try again or any other key to stop) ");
        fflush(stdin);
        scanf("%c",&thu);
    }while((thu=='y') || (thu =='Y'));
    return 0;
};

Bài toán 2:

Cho công thức sau đây:

\sum_{i=0}^{n-1}(a_i-Max)^{2}+ \sum_{i=0}^{n-1}(a_i-Min)^{2}+ \frac{n}{2}(Max-Min)^{2}

Trong đó Max Min là giá trị lớn nhất, nhỏ nhất của n số thực (được nhập vào từ thiết bi nhập xuất chuẩn) a_1, a_2,...,a_n.

Chỉ dùng duy nhất một vòng lặp for hoặc whilw, đề xuất cách thức để nhập và tính giá trị của Aver, xuất kết quả ra thiết bị nhập xuất chuẩn. Viết chương trình minh họa.

Lưu ý: không được sử dụng mảng

Ý tưởng

Từ yêu cầu của bài, ta rút ra 2 nhận xét sau:

  • Không thể dùng mảng để lưu trữ số, vậy thì phải xử lý các số ngay khi mới nhập vào, nghĩa là tìm Max, Min các số ngay trong quá trình nhập.
  • Viết lại biểu thức trên như sau:

Aver = 2\sum_{i=0}^{n-1}(a_i^2) - 2(Max+Min)\sum_{i=0}^{n-1} (a_i) + n(Max^2+Min^2) + \frac{n}{2}(Max-Min)^2

Từ đây có thể thấy việc tính toán đưa về xử lý các tổng \sum_{i=0}^{n-1}(a_i^2)(Max+Min)\sum_{i=0}^{n-1} (a_i), việc này hoàn toàn có thể thực hiện được.

Code

#include<stdio.h>
int main()
{
    int n,i=1;
    float a,max,min,s,p;
    printf("Nhap so n: ");
    scanf("%d",&n);
    printf("Nhap so thu %d: ",i++);
    scanf("%f",&a);
    s=min=max=a;
    p=a*a;
    for (;i<=n;i++)
    {
        printf("Nhap so thu %d: ",i);
        scanf("%f",&a);
        s+=a;
        p+=a*a;
        if (max<a) max=a;
        if (min>a) min=a;
    }
    printf("Aver = %f\n", (2*p - 2*(max + min)*s + n*(max*max + min*min + 0.5*(max-min)*(max-min))));
}


Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s