Xin ý tưởng: đếm xem có bao nhiêu chuỗi ký tự s có n ký tự ,mà s chỉ chứa các ký tự {0,1} và các ký tự 0 không nằm liên tiếp nhau

#1

bài tập : đếm xem có bao nhiêu chuỗi ký tự s có n ký tự ,mà s chỉ chứa các ký tự {0,1} và các ký tự 0 không nằm liên tiếp nhau

#2

Vậy những chuỗi ký tự s đó nằm ở đâu ?

#3

BT này mình chỉ xét xem tồn tại bao nhiêu xâu s chứa {0.1} và các ký tự 0 không nằm liền kề nhau thôi,và không cần xuất các chuỗi đó ra :))
các chuỗi này ko có sẵn ,mình tự tìm và đếm
mình còn gà quá k biết làm

#4

Không ! Ý mình là những chuỗi s nó nằm ở đâu ?

Vì bản chất, 1 chuỗi s chứa nhiều ký tự, vậy cái gì chứa những (nhiều) chuỗi s đó để đếm ?

#5

đọc kĩ đề đi nà, tìm trong 1 chuỗi xem có bao nhiêu chuỗi s độ dài n (s là chuỗi chỉ chứa các kí tự {0,1} mà các kí tự 0 không nằm cạnh nhau).

#6

nếu n nhỏ khoảng 20 thì cứ đệ quy thử và sai
còn lớn hơn thì làm quy hoạch động

#7

Vậy thì phải thêm “trong chuỗi s” nữa anh ạ :joy:

#8

có lẽ là nhập vào 1 chuỗi bất kỳ >n phần tử… tìm xem có bn chuỗi định dạng là chỉ có {0,1} bao gồm n ký tự… ??

#9

không phải, chuỗi mình nhập vào không có tên, giờ mình cần đếm xem có bao nhiêu chuỗi s. như là đếm xem trong lớp học có bao nhiêu bạn Minh mà có 2 mắt, 2 tay 2 chân ấy.

1 Like
#10

viết công thức đệ quy ra là thấy liền à. Công thức cực kì quen thuộc. Ko cần quy hoạch động đâu :joy:

#11

chắc 2 vòng lặp lồng nhau?

int count_s(string mystring, int n){
    int l = strlen(mystring);
    int count = 0;
    for (int i = 0; i < l - n - 1; i++) {
        if (s[i] == '0' || s[i] == '1') {
            boolean c = true;
            for (int j = i + 1; j <= i + n; j++) {
                if ((s[j - 1] == '0' && s[j] == '0') || (s[j] != '0' && s[j] != '1')) {
                    c = false;
                    break;
                }
            }
            if (c) {
                count++;
            }
        }
    }
    return count;
}

Viết chơi vậy chưa test, có gì test dùm mình nha.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?