ลำดับบอม-สวีทในโปรแกรม C

นี่คือลำดับบอม-สวีท (Baum Sweet Sequence) ลำดับฐานสอง ถ้าตัวเลข n มีจำนวน 0 ติดต่อกันเป็นคี่ ตัวเลข nth จะเป็น 0 มิฉะนั้นเป็น 1

ได้รับจำนวนธรรมชาติ n หาพจน์ที่ n ของลำดับบอม-สวีท ตรวจสอบว่ามีบล็อก 0 ติดต่อกันยาวคี่หรือไม่

ถ้าเลขคือ 4 พจน์จะเป็น 1 เพราะ 4 คือ 100 มี 0 สองตัว (คู่)

อัลกอริทึม

BaumSweetSeqTerm (G, s) -

begin
  define bit sequence seq of size n
  baum := 1
  len := number of bits in binary of n
  for i in range 0 to len, do
    j := i + 1
    count := 1
    if seq[i] = 0, then
      for j in range i + 1 to len, do
        if seq[j] = 0, then
          increase count
        else
          break
        end if
      done
      if count is odd, then
        baum := 0
      end if
    end if
  done
  return baum
end

ตัวอย่างโค้ด C++

#include 
using namespace std;
int BaumSweetSeqTerm(int n) {
    bitset<32> sequence(n); // เก็บการแทนฐานสอง
    int len = 32 - __builtin_clz(n);
    // builtin_clz() ให้จำนวนศูนย์หน้าตัว 1 แรก
    int baum = 1; // พจน์ที่ n ของลำดับบอม
    for (int i = 0; i < len;) {
        int j = i + 1;
        if (sequence[i] == 0) {
            int count = 1;
            for (j = i + 1; j < len; j++) {
                if (sequence[j] == 0) // นับศูนย์ติดต่อกัน
                    count++;
                else
                    break;
            }
            if (count % 2 == 1) // ตรวจสอบคี่หรือคู่
                baum = 0;
        }
        i = j;
    }
    return baum;
}
int main() {
    int n = 4;
    cout << BaumSweetSeqTerm(n);
}

ลำดับบอม-สวีทในโปรแกรม C

อัลกอริทึม

ตัวอย่างโค้ด C++

ผลลัพธ์