30/09/2018, 17:24

Thuật toán để tìm số các số tự nhiên ko giảm nhỏ hơn số không giảm N?

Cụ thể đề bài như sau ạ :
Một số được gọi là không giảm nếu các chữ số từ trái qua phải chỉ đơn điệu tăng hoặc bằng nhau.

Ví dụ:

123 là số không giảm
11123333 là số không giảm
112343 không phải số không giảm
Bài toán đặt ra là cho một số nguyên N, hãy xác định đó có phải là số không giảm hay không. Nếu đúng thì đếm số lượng các số không giảm nhỏ hơn N.

Gió viết 19:37 ngày 30/09/2018

Đầu tiên tìm thuật toán của số không giảm có độ dài n, có chữ số bắt đầu là st kết thúc là nd.

ví dụ số không giảm có 2 chữ số [00] -> [99]

Nhận thấy số chữ số hình thành là tổ hợp lặp

[0 1 2 3 4 # 5 # 6 7 8 9] lấy 2 vị trí

nên số cách hình thành là C_nd-st+nⁿ= 55 số

Giờ xây dựng thuật toán cho số a( lưu với vector chứa các chữ số )

function dem(v, st=0)
  res=0
  n=length(v)
  for i in range(st,v[0]):
    res+=C(9-i+n-1,n-1) ## đếm số không giảm mà có chữ số thứ n nhỏ hơn trong a
  res+=dem(v[1:],v[0])
  return res
end

Dương Phạm viết 19:33 ngày 30/09/2018

conver sang C giúp mk với

Gió viết 19:30 ngày 30/09/2018

Code demo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long ll;

ll gt[20];

ll C(int n,int k){  // to hop k n phan tu
     return gt[n]/gt[k]/gt[n-k];
}
ll dem(char *v,int n,int st){
     if(n==0) return 0;
     ll res=0;
     int i;
     for(i=st;i<v[0]-'0'; i++){
             res+=C(9-i+n-1,n-1);
     }
     res+=dem(v+1,n-1,v[0]-'0');
     return res;
}
int main(){
    int i;
    gt[0]=1;
    for(i=1;i<20;++i) gt[i]=gt[i-1]*i;
    char so[25]; // so khong giam
    scanf("%s",so);
    int n=strlen(so);
    printf("%lld\n", dem(so,n,0));
    return 0;
}

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Dương Phạm

0 chủ đề

0 bài viết

Tác giả nổi bật