Lập trình C: Solution bài tập phần mảng số
Link bài tập phần mảng: https://v1study.com/c-bai-tap-phan-mang-array-a494.html
Solution Bài tập 2 - Mảng số 1 chiều:
Bạn có thể xem video về cách làm: https://v1study.com/video-lap-trinh-c-solution-bai-tap-phan-mang-so.html
#include<stdio.h>
#include<conio.h>
#include<math.h>
void menu(void){
printf("\n1. Nhap so nguyen N (0<N<50)");
printf("\n2. Nhap mang N so thuc");
printf("\n3. Tim so lon nhat trong mang");
printf("\n4. Tim so nho nhat trong mang");
printf("\n5. Tim so duong chan lon nhat trong mang");
printf("\n6. Tim so am le nho nhat trong mang");
printf("\n7. Tim cac so chinh phuong trong mang");
printf("\n8. Tinh tong mang");
printf("\n9. Tinh trung binh cong cac phan tu mang");
printf("\n10. Tim nhung phan tu lon hon trung binh cong");
printf("\n11. Sap xep mang theo trat tu tang dan");
printf("\n12. Sap xep mang theo trat tu giam dan");
printf("\n13. Thoat");
}
void nhapN(int *N){
do{
printf("\nNhap so nguyen N (0<N<50): ");
scanf("%d",&*N);
}while(!(0<*N && *N<50));
}
void nhapMang(int N, float a[]){
int i;
printf("\nNhap lieu cho mang:");
for(i=0; i<N; i++){
printf("\nPhan tu thu %d: ",i+1);
scanf("%f",&a[i]);
}
printf("\nSau khi nhap, ta duoc:");
for(i=0; i<N; i++){
printf("\na[%d]=%g",i,a[i]);
}
}
void timMax(int N, float a[]){
int i;
float Max=a[0];
for(i=1; i<N; i++){
if(Max<a[i]){
Max=a[i];
}
}
printf("\nGia tri lon nhat trong mang la: %g",Max);
}
void timMin(int N, float a[]){
int i;
float Min=a[0];
for(i=1; i<N; i++){
if(Min>a[i]){
Min=a[i];
}
}
printf("\nGia tri nho nhat trong mang la: %g",Min);
}
void timSoDuongChanMax(int N, float a[]){
int i;
float duongChanMax=0;
for(i=0; i<N; i++){
if(a[i]>0 && a[i]==(int)a[i] && (int)a[i]%2==0 && duongChanMax<a[i]){ //Neu a[i]>0 (duong, a[i] la so nguyen, a[i] chia het cho 2, lon hon duongChanMax
duongChanMax=a[i];
}
}
if(duongChanMax==0){
printf("\nMang khong co so duong chan");
}else{
printf("\nSo duong chan Max la: %g",duongChanMax);
}
}
void timSoAmLeMin(int N, float a[]){
int i;
float amLeMin=0;
for(i=0; i<N; i++){
if(a[i]<0 && a[i]==(int)a[i] && (int)a[i]%2!=0 && amLeMin>a[i]){
//Neu a[i]<0 (am), nguyen, khong chia het cho 2,
//va lon hon amLeMin
amLeMin=a[i];
}
}
if(amLeMin==0){
printf("\nMang khong co so am le");
}else{
printf("\nSo am le nho nhat trong mang: %g",amLeMin);
}
}
void timSoChinhPhuong(int N, float a[]){
int i;
int timThay=0;
printf("\nNhung phan tu la so chinh phuong:");
for(i=0; i<N; i++){
if(a[i]>0 && sqrt(a[i])==(int)sqrt(a[i])){
printf("\na[%d] = %g",i,a[i]);
timThay=1;
}
}
if(timThay==0){
printf("\nKhong tim thay so chinh phuong trong mang");
}
}
float tinhTong(int N, float a[]){
float tong=0;
int i;
for(i=0; i<N; i++){
tong+=a[i];
}
printf("\nTong mang la: %g",tong);
return tong;
}
void tinhTBC(int N, float a[]){
float tbc=tinhTong(N,a);
printf("\nTrung binh cong cua mang: %g",tbc/N);
}
void timLonHonTBC(int N, float a[]){
int i;
float tbc=tinhTong(N,a)/N;
printf("\nTBC = %g. Nhung phan tu lon hon %g:",tbc,tbc);
for(i=0; i<N; i++){
if(a[i]>tbc){
printf("\na[%d] = %g",i,a[i]);
}
}
}
void sapXepTang(int N, float a[]){
int i, j;
float tg;
for(i=0; i<N-1; i++){
for(j=i+1; j<N; j++){
if(a[i]>a[j]){
tg=a[i];
a[i]=a[j];
a[j]=tg;
}
}
}
printf("\nSap xep mang tang dan:");
for(i=0; i<N; i++){
printf("\na[%d]=%g",i,a[i]);
}
}
void sapXepGiam(int N, float a[]){
int i, j;
float tg;
for(i=0; i<N-1; i++){
for(j=i+1; j<N; j++){
if(a[i]<a[j]){
tg=a[i];
a[i]=a[j];
a[j]=tg;
}
}
}
printf("\nSap xep mang giam dan:");
for(i=0; i<N; i++){
printf("\na[%d]=%g",i,a[i]);
}
}
int main(){
int N;
int i;
int chon;
float a[49];
menu();
while(1){
printf("\nMoi ban chon 1 muc: ");
scanf("%d",&chon);
switch(chon){
case 1:
nhapN(&N);
break;
case 2:
nhapMang(N,a);
break;
case 3:
timMax(N,a);
break;
case 4:
timMin(N,a);
break;
case 5:
timSoDuongChanMax(N,a);
break;
case 6:
timSoAmLeMin(N,a);
break;
case 7:
timSoChinhPhuong(N,a);
break;
case 8:
tinhTong(N,a);
break;
case 9:
tinhTBC(N,a);
break;
case 10:
timLonHonTBC(N,a);
break;
case 11:
sapXepTang(N,a);
break;
case 12:
sapXepGiam(N,a);
break;
case 13: return 0;
}
}
return 0;
}
Solution Bài tập 3 - Mảng số 1 chiều:
1) Cấu trúc con tối ưu
Để đếm được số cách ta có thể chia tất cả các nghiệm của tập hợp thành hai tập hợp sau:
- Các giải pháp không chứa đồng xu thứ m (hoặc Sm).
- Các giải pháp chứa ít nhất một Sm.
Gọi count (S[], m, n) là hàm đếm số cách, thì nó có thể được viết dưới dạng tổng của count(S[], m-1, n) và count(S[], m, n-Sm).
Do đó, bài toán có thuộc tính cấu trúc con tối ưu vì bài toán có thể được giải quyết bằng cách sử dụng các giải pháp cho bài toán con.
2) Triển khai giải pháp
Sau đây là một cách triển khai đệ quy đơn giản cho bài toán Change Coin đã được phân tích như trên:
// Sử dụng thuật toán quay lui (đệ quy) cho bài toán #include<stdio.h> // Trả về số cách tính tổng coin // S[0...m-1] để có tổng n int count(int S[], int m, int n){ // nếu n là 0 thì có 1 cách if (n == 0) return 1; // nếu n nhỏ hơn 0 thì không có cách nào if (n < 0) return 0; // nếu không có coin nào và n // lớn hơn 0, thì cũng không // có cách nào if (m <=0 && n >= 1) return 0; // gọi đệ quy để đếm số cách return count( S, m - 1, n ) + count( S, m, n-S[m-1] ); } int main(){ int i, j; int arr[] = {1, 2, 3}; int m = sizeof(arr)/sizeof(arr[0]); printf("%d ", count(arr, m, 4)); return 0; }