Lập trình C: Solution bài tập phần vòng lặp

Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực

Bài tập 3:

Ý 15:

Code C:

#include <stdio.h>
 
int main(){
    int N;
    printf("\nMoi nhap N: ");
    scanf("%d", &N);
    int dem;
    
    for(int i = 2; i <= N; i++){
        dem = 0;
        while(N % i == 0){
            ++dem;
            N /= i;
        }
        if(dem){
            if(dem > 1) printf("%d^%d", i, dem);
            else printf("%d", i);
            if(N > i){
                printf(" * ");
            }
        }
    }
    
    return 0;    
}

Code C++:

#include <iostream>
using namespace std;
 
int main(){
    int N;
    cout << "\nMoi nhap N: ";
    cin >> N;
    int dem;
    
    for(int i = 2; i <= N; i++){
        dem = 0;
        while(N % i == 0){
            ++dem;
            N /= i;
        }
        if(dem){
            cout << i;
            if(dem > 1) cout << "^" << dem;
            if(N > i){
                cout << " * ";
            }
        }
    }

  return 0;    
}

Code C++ sử dụng map:

#include <iostream>
using namespace std;
#include <map>
 
int main(){
    int N;
    cout << "\nMoi nhap N: ";
    cin >> N;
    
    map<int, int> m;
    for(int i = 2; i <= N; i++){
        while(N % i == 0){
            m[i]++;
            N /= i;
        }
    }
    
    for(auto it : m){
        cout << it.first << " " << it.second << "\n";
    }
  
  return 0;
}

Bài tập 7:

#include<bits/stdc++.h>
using namespace std;

int main(){
  int a,b,c,nam,ngay,tong;
  cin>>a>>b>>c;
  c=c-1;
  nam=(a-1950)*365;
  if(b==1){
    ngay=120+c;
  }else if(b==6){
    ngay=151+c;
  }else if(b==7){
    ngay=181+c;
  }else if(b==8){
    ngay=212+c;
  }else if(b==9){
    ngay=243+c;
  }else if(b==10){
    ngay=273+c;
  }else if(b==11){
    ngay=304+c;
  }else if(b==12){
    ngay=334+c;
  }
  tong = nam + ngay;
  if(b<=2){
    for(int i=1950;i<a;i++){
      if(i%4==0){
        tong++;
      }
    }
  }else{
    for(int i=1950;i<=a;i++){
      if(i%4==0){
        tong++;
      }
    }
  }
  cout<<tong%7;
  
  return 0;
}

Bài tập 8:

#include<bits/stdc++.h>
using namespace std;

int main()
{
  string s;
  getline(cin, s);
  int tong_chan=0, tong_le=0;
  for(int i=0; i<s.length(); i++){
    if(i%2==0){
      if(s[i]=='1'){
        tong_chan++;
      }
    }
    else if(i%2==1){
      if(s[i]=='1'){
        tong_le++;
      }
    }
  }
  if((tong_chan==tong_le) || (abs(tong_chan-tong_le)>=2)){
    cout<<"0";
  }
  else{
    if(tong_chan>tong_le){
      int vt=0;
      for(int i=0; i<s.length(); i+=2){
        if(s[i]=='1'){
          vt= i+1;
          break;
        }
      }
      cout<<vt;
    }
    else if(tong_le>tong_chan){
      int vt=0;
      for(int i=1; i<s.length(); i+=2){
        if(s[i]=='1'){
          vt= i+1;
          break;
        }
      }
      cout<<vt;
    }
  }
  
  return 0;
}

Bài tập 10:

Để giải bài toán này, ta có thể dùng quả trứng 1 thả với mỗi x tầng ví dụ x=10 tầng. Quả trứng 1 sẽ đóng vai trò thu hẹp khoảng cần tìm vào trong 10 tầng, sau đó dùng quả trúng 2 để tìm tầng thỏa mãn trong 10 tầng đó. Ví dụ nếu tầng cần tìm là 93, quả trứng 1 sẽ được thả lần lượt các tầng 10, 20, 30, 40, 50, 60, 70, 80, 90 và vỡ ở tầng 100. Sau đó ta biết N cần tìm trong khoảng 90-100 và dùng quả trứng 2 để tìm, cần 3 lần thả nữa 91, 92, 93 là trứng vỡ, suy ra N = 93.

Đây là 1 cách giải tốt, nếu 1 < N < 10, ta chỉ cần 2-10 lần thả trứng. Nhưng nếu 81<N<90, t cần đến 18 lần thả. Vậy cần chia khoảng để thả quả trứng 1 là bao nhiêu để tối ưu ?. Hãy nhớ rằng chúng ta tìm cách giải với số lần thả nhỏ nhất, chứ không phải tìm số lần cần thả trung bình.

Ta thấy số_lần_thả_trứng_ít_nhất sẽ tăng tỉ lệ thuận với tầng. Nếu quả trứng 1 vỡ ở tầng x thì ta cần nhiều nhất 9 lần thả quả trứng 2. Cho nên, thay vì việc thả trứng 1 mỗi 10 tầng, ta sẽ điều chỉnh khoảng cách đó, sao cho nó lớn ở những tầng dưới và nhỏ dần ở những tầng trên. Qua đó ta giảm số lần phải thả trong trường hợp xấu nhất, khi đó số lần tối đa phải thả quả trứng 2 sẽ giảm cùng tốc độ với tốc độ tăng của số lần (tương đương với độ cao) phải thả quả trứng 1.

Số lần thả trứng 1 Khoảng cách giữa 2 tầng
# 1 x
# 2 x-1
# 3 x-2
# 4 x-3
# 5 x-4
# ... ...

Suy ra: (x + 1) * x / 2 >= 100.
x ≥ 13.65097. làm tròn đến giá trị đầu tiên để tổng >= 100. => x = 14.

Vậy ta bắt đầu từ tầng 14. Cần tối đa 14 lần thả. Độ phức tạp O(\sqrt{n}n)
Với n nhỏ, 2 cách trên gần như tương đương.

Số lần thả trứng 1 Tầng
1 14
2 27
3 39
4 50
5 60
6 69
7 77
8 84
9 90
10 95
12 99
12 100
 

Bài tập 11:

#include<iostream>

using namespace std;

int main(){
    int N,cnt=0;
    cin >> N;
    for(int i=1; i<N; i++){
        cnt+=(N-1)/i;
    }
    cout << cnt << endl;

    return 0;
}

Bài tập 12:

#include<iostream>
#include<math.h>
using namespace std;

bool check(int n) {
    int m= sqrt(n);
    m= m*m;
    if(m==n) return true;
    else return false;
}

int countt(int n) {
    int cnt= 0;
    for(int a=1; a<sqrt(n); a++) if(n%a==0) cnt++;
    if(check(n)==true) cnt= cnt*2+1;
    else cnt= cnt*2;
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin>>n;
    int ans= 0;
    for(int c=1; c<n; c++){
        m= n-c;
        ans+=(countt(m));
    }
    cout<<ans<<endl;
}
» Tiếp: Solution bài tập phần mảng số
« Trước: Solution Bài tập phần điều kiện
Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực
Copied !!!