Bài tập 3

Bài 3: Tính F(x)

Cho hàm F(x), x ≥ 0 được định nghĩa như sau:

F(x) = x, nếu x ≤ 9

F(x) = F(S(x)), nếu x > 9

Trong đó S(x): tổng các chữ số của x.

Yêu cầu: Hãy viết chương trình tính F(n!), với 1 <= n <= 500.

Giải:

Khi nói đến tổng các chữ số của 1 số ta liên tưởng ngay đến tính chất chia hết cho 3 và chia hết cho 9.

Nhắc lại kiến thức cũ:”Một số chia hết cho 9(hay 3) thì có tổng các chữ số chia hết cho (hay 3).

Giá trị của hàm F(x) chỉ nằm trong khoảng từ 1 đến 9.Nếu làm theo định nghĩa thì số lần lặp sẽ cực kì lớn chưa kể với n! (1<=n<=500) nên cần phải sử dụng một số tính chất để làm đơn giản bài toán.

Trở lại với tính chất trên, ta thấy ngay n! với n>=6 luôn chia hết cho 9 và S(n) cũng chia hết cho 9.Dễ dàng chứng minh bằng qui nạp ta có ngay số cuối cùng của dãy số trên là số từ 1 đến 9 và chia hết cho 9.

Suy ra với n>= 6 , F(n!)=9.

Ở đây ta không dùng tính chất chia 3 vì đơn giản trong khoảng 1 đến 9 có 3 số chia hết cho 3.

Với các giá trị n thuộc từ 1 đến 6 ta có thể vét cạn các giá trị này.

n	1	2	3	4	5
F(n)	1	2	6	6	3

Mã nguồn:

#include <stdio.h> int F(int a); int F(int a) {        int result;        switch(a){               case 1:result=1;break;               case 2:result=2;break;               case 3:result=6;break;               case 4:result=6;break;               case 5:result=3;break;               default:result=9;        }        return result; }

Bài tập 2

Bài 2: Xem công thức tính sau đây (đề thi tuyển sinh cao học ngành KHMT, năm 2011):

Trong đó Max, Min lần lượt là giá trị lớn nhất, nhỏ nhất của n số thực (được nhập vào từ thiết bị nhập chuẩn) a₀, a₁, …, a_n-1.

Chỉ dùng duy nhất 1 vòng lặp (for hoặc while), đề xuất cách thức để nhập n số thực như trên và tính giá trị của biểu thức Aver, xuất kết quả tính ra thiết bị xuất chuẩn. Viết chương trình để minh họa đề xuất đó.

Lưu ý: Phần này sinh viên chưa học về mảng, như vậy vấn đề chính của bài toán này là không thể dùng mảng để lưu giá trị của n số thực nói trên. Như vậy phải đề xuất một giải pháp “thông minh” để nhập và tính toán mà không đưa trước các số thực này vào mảng.

Giải:

Điều kiện không dùng vòng lặp là hiển nhiên bởi tính đến lúc viết  tôi vẫm chưa học mảng.

Nhìn vào đề bài ta thấy ngay cần phải tách các giá trị Max,Min là các số chưa biết vì đến cuối vòng lặp ta mới xác định được 2 số này.

Ta có :

Chỉ cần tính  và  sau khi lặp được các giá trị Max, Min thế vào Aver ta được ngay đáp số với chỉ 1 vòng lặp

Mã nguồn:

#include <stdio.h> void main() {        int n,i,j,max,min;        float aver1,aver2;        aver1=aver2=0;        min=2147483648;        max=-1*min;        printf("Input n = ");        scanf("%d",&n);        for (i=1;i<n;i++)        {               printf("nhap so thu %d\t",i);               scanf("%d",&j);               aver1 += j;               aver2 += j*j;               if (min >= j)                      min=j;               if (max <= i)                      max=j;        }        float aver;        aver= 2*aver2 -2*(max+min)*aver1+(n/2.0)*(max-min)*(max-min)+max*max+min*min;        printf("%f",aver); }

Bài tập 1

Bài 1: Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 10⁹

Ví dụ:

Số nhập vào là A	Số xuất ra là N
8	4
13	13

 Giải:

Để tìm N nhỏ nhất ta không thể cho N chạy từ 1 đến A, rồi kiểm tra N^N có chia hết cho A không. Nếu A nhỏ thì chỉ không quan tâm nhưng khi A lớn thì giá trị N^N rất lớn có thể xảy ra tràn số.

VD: A =999907 thì N =999907 thì đôi khi thuật toán rất chậm và có thể xảy ra tràn số.Do đó ta phải đi theo con đường khác.

Như đã biết một số nếu là hợp số có thể phân tích thành tích các thừa số là các số nguyên tố. Hiển nhiên bởi số nguyên tố là số chỉ chia hết cho 1 và chính nó.

Từ điều này ta có điều kiện cần để một số chia hết cho A cho trước thì nó phải chia hết hay tích của nó có chứa tất cả thừa số nguyên tố của A.

Xét số aⁿ để chia hết các thừa số nguyên tố của A thì a cũng phải thỏa điều kiện đó.

Có thể hiều là : A =a₁^b1 x a₂^b2 x … x a_n^bn.({a_n} là tập hợp thừa số nguyên tố của  A)

aⁿ mod A = 0 => (aⁿ mod a₁ = 0) /\ (aⁿ mod a₂= 0) /\ …/\ (aⁿ mod a_n=0)

=>(a mod a₁=0) /\ (a mod a₂ = 0) /\ (a mod a₃=0) /\ …/\ (a mod a_n=0)

a nhỏ nhất chính là tích của a₁,a₂,…,a_n.

Từ đó ta xét với N^N = aⁿ.

N nhỏ nhất chính là N=a₁ x a₂ x a₃ x … x a_n.

Đây mới chỉ là điều kiện cần, điều kiện đủ là cần phải có N lớn hơn hoặc bằng số mũ lớn nhất của các thừa số nguyên tố của A, chính là max{b_n}.

Từ đây ta hình thành thuật toán:

Bởi đề bài yêu cầu chỉ cần tính N nhỏ nhất ta chỉ cần lưu tích của các thừa số nguyên tố của A, sau đó là kiểm tra xem N có lớn hơn hoặc bằng  max {b_n}, nếu không thì nhân N với số nguyên dương nhỏ nhất khác 1 là số 2, nếu vẫn chưa được thì nhân tiếp với 3… dừng đến khi N lớn hơn

max{b_n}.Nhưng còn 1 trường hợp là số nhân tiếp có thừa số nguyên tố có số mũ lớn nhất.Trường hợp này ta phải phân tích nó ra xem thử số mũ của thừa số nguyên tố ấy ứng với nó là bao nhiêu,gọi là k.Cụ thể là giá trị để N so sánh sẽ không còn là max{b_n} mà sẽ giảm đi (k+1) lần.

Trong trường hợp có nhiều thừa số có cùng số mũ lớn nhất của A thì chỉ lấy số nhỏ nhất bởi chỉ cần nhân N với hợp số của số nhỏ nhất cũng đủ rồi bởi A  ≤ 10⁹.

VD: Với trường hợp đơn giản nhất là N=2x3x4.

N^N=(2 x 3 x 4)^{2 x 3x4} >>10⁹.

Các bạn muốn trường hợp lớn hơn có thể dùng mảng để giải quyết hoàn toàn vấn đề còn lại.

Mã nguồn tham khảo:

#include <stdio.h> long minN(long a) {        long i,n=1;        int dem,max=0,max1;        for (i=2;a > 1;i++)        {               if (a % i ==0)               {                      for (dem =0;a % i == 0;a /= i,dem ++);                      if (dem > max)                      {                            max = dem;                            max1 =i;                      }                      n=i*n;               }        }        int j1,j = 2;        long max2;        while (n < max2)        {               max2=max;               j1=j;               for(dem=1;j1 % max1 ==0;j1 /= max1,dem++);               max2 /= dem;               n += n;               j++;        }        return n; }