Chuỗi Đối xứng và dãy số nguyên

[dieulinh_hg]

Nếu cho em doạn code thì em cảm ơn nhiều
Bai 1:Chuỗi đối xứng

Một chuỗi được gọi là đối xứng nếu nó không ít hơn một ký tự và nếu ta đọc từ trái sang phải hay từ phải sang trái đều được kết quả giống nhau.

Ví dụ:”A”;”TET”;”CAOOAC” là các chuỗi đối xứng.

Viết chương trình nhập vào một chuỗi ký tự S,có chiều dài n(1≤n ≤1000).hay cho biết chiều dài chuỗi con đối xứng dài nhất.Chuỗi con của S là chuỗi gồm một số ký tự liên tiếp nhau trong S có độ dài nhỏ hơn hoặc bằng n.

Dữ liệu vào được cho trong tập tin văn bản CHUOI.INP gồm 2 dòng .

-dòng đầu ghi số n

-dòng sau ghi n ký tự liên tiếp gồm các chữ cái in hoa(A dến Z)

Dữ liệu ra cần được ghi vào tập tin văn bản CHUOI.UOT gồm một số duy nhất là độ dài của chuỗi con đối xứng dài nhất.

Bài 2ãy số nguyên

Cho dãy số nguyên …, fi, fi+1, … thoả tính chất mỗi số trong dãy bằng tổng của hai số sát trước số đó: fn=fn-1+fn-2.Biết fi và fj, i≠j.Tính fn.

Dữ liệu vào dược ghi trong tạp tin văn bản DAYSO.INP

-dòng đầu ghi số tự nhiên k cho biết số lượng các test.

-tiếp theo là k dòng, mỗi dòng ứng với một test chúa 5 số nguyên cách nhau ít nhất một khoảng trắng, bao gồm i fi j fj n trong đó -1000 ≤ i, j ≤ 1000;một số trong dãy đêu nằm trong khoảng -2 tỷ dến 2 tỷ.

Dữ liệu ra cần được ghi vào tập tin văn bản DAYSO.OUT gồm k dòng, mỗi dòng là một giá trị fn của test tương ứng.

Ý nghĩa của test:

Test 1:Biết f3=5, f -1=4, cần tính f5. Kết quả :f5=12

Test 2:Biết f6=8, f2=1, cần tính f9. Kết quả: f9=34

Bạn dieulinh_hg lưu ý:
- Không spam bài viết của mình lên diễn đàn nhé.
- Vui lòng đọc nội quy trước khi gửi bài.
- Nếu tiếp tục vi phạm, toàn bộ bài viết của bạn sẽ bị xóa bỏ mà không cần thông báo trước.

[metal_shield]

Hướng dẫn bài 1:

Xuất phát từ kí tự thứ i
Khởi tạo đầu = i, cuối = i;
-Nếu a[i] = a[i-1] -> đầu --;
while (a[dau] = a[cuoi]) -> đầu --;cuối++,
-> cập nhật độ dài và xâu đối xứng

-Nếu a[i] = a[i+1]-> cuối ++;
while (a[dau] = a[cuoi]) -> đầu --;cuối++,
-> cập nhật độ dài và xâu đối xứng

-Đầu --, cuối ++,
while (a[dau] = a[cuoi]) -> đầu --;cuối++,
-> cập nhật độ dài và xâu đối xứng

Bài 2 đang nghĩ

[metal_shield]

Bài 2 liên quan tới toán học khá nhiều. Bạn phải tìm ra công thức liên quan giữa fn với fi và fj.

Giả sử j<i

Ta thấy:f(j+1) = f(j)+k
-> f(j+2) = f(j) + f(j+1) = 2f(j) + k
-> f(j+3) = 3f(j) + 2k
-> f(j+4) = 4f(j) + 3k
-> f(j+5) = 5f(j) + 5k
..
->f(j+t) = tf(j) + a[t].k ( Trong đó a[t] là số fibonacy thứ t)

Theo tính toán thì số fibonacy thứ 45 là 1.1 tỉ, số 46 là 1.8 tỉ và số 47 là 2.9 tỉ
Như vậy nếu (k != 0) thì i và j không thể cách nhau tới quá 45 đơn vị, nếu không sẽ xảy ra trường hợp các số trong dãy vượt quá khoảng -2 tỉ tới 2 tỉ

Trong các trường hợp i và j cách nhau không quá nhiều, bạn nên làm 1 mảng lưu các số fibonacy từ 1 tới 45. Dựa vào công thức của mình, bạn sẽ tính ra k theo công thức f(i) = (i-j)f(j) +a[i-j]k

Sau khi có k, bạn tính f(n) cũng theo công thức trên.

[dieulinh_hg]

hix, em dốt toán lắm em mới học lập trình có 3 tháng thôi làm sao em có thể giải được bài toán olympic dó được,giúp em nha,em cảm ơn,em sẽ cố gắng

[metal_shield]

hix, em dốt toán lắm em mới học lập trình có 3 tháng thôi làm sao em có thể giải được bài toán olympic dó được,giúp em nha,em cảm ơn,em sẽ cố gắng

Bạn mới học, sao lại thích làm bài olimpic chứ? Làm những bài cơ bản trứoc. Nếu nó fù hợp với trình độ của bạn, thày mới giao cho chứ. Bạn làm đựoc, gặp khó khăn rồi post lên hỏi. Còn lại thì ko ai giúp code cho bạn đâu

[dieulinh_hg]

em làm đề tài đó mà!thầy giáo trên trường bắt làm để làm quen vói v iệc làm dề tài đó anh!nhưng ma em sẽ cố gắng, có gì thì anh giúp dỡ em nghen,em nghĩ là em làm không ra

[dieulinh_hg]

anh ơi phần đầu thế này có dược không anh
còn phần cập nhật độ dài và xâu đx làm sao em kô hiểu anh à

#include<conio.h>
#include<iostream.h>
#include<string.h>
#include<stdio.h>
void main()
{
	slrscr();
	int i;
	char dau=i,cuoi=i;
	char s[1000];
	cout<<"nhap chuoi";
	gets(s);
	int l=strlen(s);
	for(int i=0;i<l/2;i++)
	if(s[i]=s[i-1])
	dau--;
	while(s[dau]=s[cuoi])
	{
		dau--;
		cuoi==;
	}

Lưu ý bỏ code vào thẻ code tham khảo cách bỏ code vào thẻ code tại đây
Posted by iamvtn

[sieuphuong]

còn phần cập nhật độ dài và xâu đx làm sao em kô hiểu anh à

Có anh đây em à . ^^ . Phần cập nhật độ dài thì bạn dùng 2 biến , một biến là dai và 1 biến là daimax . Mỗi lần tìm được chuỗi đối xứng mới thì cập nhật độ dài cho dai và so sánh nó với daimax , nếu dai>daimax thì daimax=dai . Phần cập nhật xâu chính là cập nhật chỉ số đầu và cuối của chuỗi đối xứng dài nhất trong chuỗi đó bạn .

[rox_rook]

Bài 1 nó nằm ở đây nè, giải thuật cũng đơn giản, vòng lặp thôi không có gì hết, nếu dãy không liên tục thì mới mệt T_T( QHD 99% ). Hồi đầu đọc cái đề hấp ta hấp tấp nên....hichic.
ps : Nếu muốn học thực sự, thì nên suy nghĩ trước khi đọc lời giải.

#include <iostream> 
#include <fstream> //input file 
#include <vector>  //vector string 
#include <string>  //string 
#include <cctype>  //isalpha, toupper 

using namespace std; 

//function prototype 
bool IsPalindromeString(string ss); 

int main() 
{ 
    vector<std::string> lines; 
    /*each line from the file gets read into this,  
     before being added to `lines'*/ 
    string line; 
     
    std::ifstream client_file("a.txt"); 
    if(!client_file || !client_file.is_open()) 
    { 
        cerr << "Couldn't open file!"; 
        return 1; 
    } 

    while(getline(client_file,line)) 
    { 
        lines.push_back(line); 
    } 
   
    int max_length = 0; 
   
    for(int pos = 0; pos <= line.length(); pos++) 
    { 
        for(int _q = line.length(); _q > pos; _q--) 
        { 
            if(IsPalindromeString(line.substr(pos, _q))) 
            { 
                if(_q - pos > max_length) 
                    max_length = _q - pos; 
             
            } 
        } 
    } 

    std::cout << "The maximum Palindrome String is : " 
              << max_length << std::endl; 
         
    return 0; 
} 

   
bool IsPalindromeString(string ss) 
{ 
    string sub_string = ss; 
    int position = 0; 
    for(int x = 0; x < ss.length(); x++) 
    { 
        if (isalpha(ss[x])) 
            sub_string[position++] = toupper(ss[x]); 
    } 
        
    ss = sub_string.substr(0, position); 
    for(int x = 0; x < position/2; x++) 
    { 
        if (ss[x] != sub_string[position-1-x] ) 
            return false; 
        return true; 
    } 
} 

[dieulinh_hg]

em cảm ơn anh nhưng doạn code em kô hiểu gì cả nó vượt quá khả năng của em
về lập trình c++ thì em mới học tới con trỏ à!hihi
nhưng cũng cảm ơn anh rất nhiều
em sẽ làm dược bài 2