Làm thế nào để nối 2 mảng chứa kí tự

leh · July 24, 2019, 5:29am

Có a[1]=A; a[2]=B;
a[i]=a[i-1]+a[i-2];
VD
input i=3 output a[3]=BA
input i=4 output a[4]=BAB
input i=5 output a[4]=BABBA

mình lập trình như sau nhưng sai, phải sửa lại như nào ạ?

#include<stdio.h>
#include<math.h>
#include<string.h>
int main(){
	long long n,i;
	char a[100000];
	scanf("%lld",&n);
	a[1]=65;
	a[2]=66;
	for(i=3;i<=n;i++){
		a[i]=strcat();
	}
	printf("%c",a[n]);
}

rogp10 · July 24, 2019, 4:10am

Nối chuỗi tới O(N^2) lận, bây giờ tìm công thức truy hồi là O(NlogN)

Quang_Nhat_03 · July 26, 2019, 11:01am

Tham khảo cách code tính dãy fibonaci đi bạn

hungaya · July 27, 2019, 12:46pm

Viết binary tree rồi dùng duyệt tree in kết quả.

Mỗi node đại diện cho một a_i, thuộc tính index của node bằng giá trị i của a_i
Với node lá, a₁ dùng subclass A thay thế, a₂ dùng subclass B thay thế.

Theo công thức: a_n = a_n-1 + a_n-2, thì node a_n cũng được tạo, với left(a_n) = a_n-1, và right(a_n) = a_n-2.

#include <iostream>

struct node {
    node *left{nullptr};
    node *right{nullptr};
    int index{0};
    
    node() {}
    node(node* l, node* r): left{l}, right{r}, index{l->index + 1} {}
    
    virtual ~node() {
        if (index > 3) {
            right = nullptr;
            if (left) { delete left; left = nullptr; }
        } else {
            if (left) { delete left; left = nullptr; }
            if (right) { delete right; right = nullptr; }
        }
    }
    
    virtual void print() {
        if (left) left->print();
        if (right) right->print();
    }
};

struct A : public node {
    A() { index = 1; }
    void print() override {
        std::cout << 'A';
    }
};

struct B : public node {
    B() { index = 2; }
    void print() override {
        std::cout << 'B';
    }
};

int main() {
    int n;
    std::cin >> n;
    
    if (n < 1) { return 0; }
    if (n == 1) { std::cout << "A\n"; return 0; }
    if (n == 2) { std::cout << "B\n"; return 0; }
    
    node *root = new node {new B, new A};
    for (int i = 3; i < n; i++) {
        node *temp = root;
        root = new node {temp, temp->left};
    }
    
    root->print();
    std::cout << std::endl;
    
    delete root;
}

kiencon · July 28, 2019, 2:02am

em nó còn chưa biết cấp phát động, string hay char mà mấy chú viết kiểu đó sao nó hiểu @@
bài toán đơn giản như cộng dãy fibonacy tuy nhiên thay vì số thì đây là ký tự và chuỗi. Bạn cần có 1 cái mảng chứa được chuỗi ký tự, để ý thấy bạn đang code C và cấp phát tĩnh, nếu chưa biết cấp phát động thì cứ tạo 1 cái mảng 2 chiều để lưu. 1 hàm cộng chuỗi rồi viết theo kiễu tạo ra dãy fibonacy là ok! giảm scoped lại vì bộ nhớ stack có giới hạn tạo cái mảng a[10][10] để test là đủ.

Duong_Act · July 28, 2019, 2:40am

1.Tính độ dài chuỗi sau khi cộng.
2.Khai báo mảng có độ dài đã tính để lưu.
3.Dùng for và memcpy để copy mảng con vào mảng tổng.

hungaya · July 28, 2019, 4:32am

Theo yêu cầu, không C++, không cấp phát động

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

int main() {
    int n;
    scanf("%d", &n);
    
    if (n < 1) { return 0; }
    if (n == 1) { printf("A\n"); return 0; }
    if (n == 2) { printf("B\n"); return 0; }
    
    long f1 = 1, f2 = 2;
    long t;
    for (int i = 3; i <= n; i++) {
        t = f2;
        f2 = f1 + f2;
        f1 = t;
    }
    
    long size = f2;
    char str[size + 1];
    
    str[0] = 'B';
    str[1] = 'A';
    
    f1 = 1; f2 = 2;
    for (int i = 3; i <= n; i++) {
        memcpy(str + f2, str, f1);
        t = f2;
        f2 = f1 + f2;
        f1 = t;
    }
    str[size] = '\0';
    
    printf("%s\n", str);
}

(dễ toi vì thiếu bộ nhớ trong stack)