C++ 中的维思序列

2025 年 5 月 23 日 | 阅读 9 分钟

引言

遵循黄金比例，Wythoff 序列是组合博弈论中用于玩家移动的数学组合。它以 Willem Abraham Wythoff 的名字命名，他根据斐波那契数创建了一个与黄金分割有着奇特关系的序列。在本文中，我们将讨论 Wythoff 序列并提供一篇关于生成它的 C++ 代码的文章。

问题陈述

Wythoff 序列由两个交错序列组成，分别称为下 Wythoff 序列和上 Wythoff 序列，表示为

A(n) = floor(n * φ)

B(n) = A(n) + n

其中 φ (phi) = (1 + sqrt(5)) / 2 是黄金比例。

我们的目标是使用 C++ 生成并显示 Wythoff 序列的前 N 项。

数学背景

Wythoff 序列与黄金比例密切相关，这确保了数字分布良好而不会聚集。序列定义为

下 Wythoff 序列： A(n) = floor(n * φ)
上 Wythoff 序列： B(n) = A(n) + n

这些序列在 Wythoff 游戏和 Nim 等组合游戏中扮演着关键角色。

示例 1

让我们看一个 C++ 程序来生成并显示 Wythoff 序列的前 N 项。

 
#include <iostream>
#include <cmath>
using namespace std;

const double PHI = (1 + sqrt(5)) / 2;  // Golden ratio

// Function to generate and display the Wythoff sequence
void generateWythoffSequence(int N) {
    cout << "Wythoff sequence (first " << N << " terms):" << endl;
    cout << "Lower Sequence: ";
    for (int i = 1; i <= N; i++) {
        cout << (int)floor(i * PHI) << " ";
    }
    cout << "\nUpper Sequence: ";
    for (int i = 1; i <= N; i++) {
        cout << (int)floor(i * PHI) + i << " ";
    }
    cout << endl;
}

int main() {
    int N;
    cout << "Enter the number of terms: ";
    cin >> N;
    generateWythoffSequence(N);
    return 0;
}   

输出

 
Enter the number of terms: 10
Wythoff sequence (first 10 terms):
Lower Sequence: 1 3 4 6 8 9 11 12 14 16
Upper Sequence: 2 5 7 10 13 15 18 20 23 26

代码解释

设置 PHI 的值： 我们事先通过 (1 + sqrt(5)) / 2 计算 φ。
在 for 循环中生成序列： 使用 floor(n * PHI) 计算下序列，使用 floor(n * PHI)+n 计算上序列。
用户输入 N 的值，程序依次返回两个序列的前 N 个元素。

示例 2

让我们再举一个例子来说明 C++ 中的Wythoff 序列。

 
#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <fstream>
#include <stdexcept>
#include <algorithm>

using namespace std;

const double PHI = (1 + sqrt(5)) / 2;  // Golden ratio

class WythoffSequence {
private:
    int N;  
    vector<int> lowerSeq;
    vector<int> upperSeq;

    // Function to generate the sequences
    void generateSequences() {
        for (int i = 1; i <= N; i++) {
            int lowerValue = static_cast<int>(floor(i * PHI));
            int upperValue = lowerValue + i;
            lowerSeq.push_back(lowerValue);
            upperSeq.push_back(upperValue);
        }
    }

public:
    // Constructor
    WythoffSequence(int num) {
        if (num <= 0) {
            throw invalid_argument("N must be a positive integer.");
        }
        N = num;
        generateSequences();
    }

    // Function to display the sequences
    void displaySequences() const {
        cout << "\nWythoff sequence (first " << N << " terms):\n";
        cout << "Lower Sequence: ";
        for (int val : lowerSeq) {
            cout << val << " ";
        }
        cout << "\nUpper Sequence: ";
        for (int val : upperSeq) {
            cout << val << " ";
        }
        cout << endl;
    }

    // Function to search for an element in the sequence
    bool searchElement(int value) const {
        return (find(lowerSeq.begin(), lowerSeq.end(), value) != lowerSeq.end() ||
                find(upperSeq.begin(), upperSeq.end(), value) != upperSeq.end());
    }

    // Function to save the sequence to a file
    void saveToFile(const string &filename) const {
        ofstream file(filename);
        if (!file) {
            cerr << "Error opening file for writing!\n";
            return;
        }
        file << "Wythoff sequence (first " << N << " terms):\n";
        file << "Lower Sequence: ";
        for (int val : lowerSeq) {
            file << val << " ";
        }
        file << "\nUpper Sequence: ";
        for (int val : upperSeq) {
            file << val << " ";
        }
        file << endl;
        file.close();
        cout << "Sequence saved to " << filename << endl;
    }
};

int main() {
    try {
        int N;
        cout << "Enter the number of terms: ";
        cin >> N;

        WythoffSequence wythoff(N);
        wythoff.displaySequences();

        // Search for an element
        int searchVal;
        cout << "Enter a number to search in the sequence: ";
        cin >> searchVal;
        if (wythoff.searchElement(searchVal)) {
            cout << searchVal << " is present in the sequence.\n";
        } else {
            cout << searchVal << " is not found in the sequence.\n";
        }

        // Save sequence to a file
        wythoff.saveToFile("wythoff_sequence.txt");

    } catch (const exception &e) {
        cerr << "Error: " << e.what() << endl;
    }

    return 0;
}   

输出

 
Enter the number of terms: 20

Wythoff sequence (first 20 terms):
Lower Sequence: 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24 25 27 29 30 32 
Upper Sequence: 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39 41 44 47 49 52 
Enter a number to search in the sequence: 23
23 is present in the sequence.
Sequence saved to wythoff_sequence.txt

Wythoff 序列的应用

在组合博弈论中，它用于 Wythoff 游戏和其他类似的两人游戏。
在数学中，它出现在与斐波那契和黄金比例相关的研究中。
在优化中，它有助于在两个或多个方之间分配资源。

示例 3

让我们再举一个例子来说明 C++ 中的Wythoff 序列。

 
#include <iostream>
#include <cmath>
#include <vector>
#include <thread>
#include <mutex>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <chrono>
#include <algorithm>

using namespace std;
using namespace std::chrono;

const double PHI = (1 + sqrt(5)) / 2;  // Golden Ratio

class WythoffSequence {
private:
    int N;
    vector<int> lowerSeq;
    vector<int> upperSeq;
    unordered_map<int, pair<int, int>> memoization;
    mutex mtx;

    // Function to compute a single Wythoff number
    pair<int, int> computeTerm(int i) {
        if (memoization.find(i) != memoization.end()) {
            return memoization[i];
        }
        int lowerValue = static_cast<int>(floor(i * PHI));
        int upperValue = lowerValue + i;
        memoization[i] = {lowerValue, upperValue};
        return {lowerValue, upperValue};
    }

    // Function to generate sequences using multithreading
    void generateSequences() {
        vector<thread> threads;
        for (int i = 1; i <= N; i++) {
            threads.emplace_back([this, i]() {
                pair<int, int> values = computeTerm(i);
                lock_guard<mutex> lock(mtx);
                lowerSeq.push_back(values.first);
                upperSeq.push_back(values.second);
            });
        }
        for (auto& th : threads) {
            th.join();
        }
    }

public:
    // Constructor
    explicit WythoffSequence(int num) {
        if (num <= 0) {
            throw invalid_argument("N must be a positive integer.");
        }
        N = num;
        auto start = high_resolution_clock::now();
        generateSequences();
        auto end = high_resolution_clock::now();
        cout << "\nSequence generated in "
             << duration_cast<milliseconds>(end - start).count()
             << " ms.\n";
    }

    // Function to display sequences
    void displaySequences() const {
        cout << "\nWythoff sequence (first " << N << " terms):\n";
        cout << "Lower Sequence: ";
        for (int val : lowerSeq) {
            cout << val << " ";
        }
        cout << "\nUpper Sequence: ";
        for (int val : upperSeq) {
            cout << val << " ";
        }
        cout << endl;
    }

    // Function to check if a number exists in the sequence
    bool searchElement(int value) const {
        return (find(lowerSeq.begin(), lowerSeq.end(), value) != lowerSeq.end() ||
                find(upperSeq.begin(), upperSeq.end(), value) != upperSeq.end());
    }

    // Function to save the sequence to a file
    void saveToFile(const string &filename) const {
        ofstream file(filename);
        if (!file) {
            cerr << "Error opening file!\n";
            return;
        }
        file << "Wythoff sequence (first " << N << " terms):\n";
        file << "Lower Sequence: ";
        for (int val : lowerSeq) {
            file << val << " ";
        }
        file << "\nUpper Sequence: ";
        for (int val : upperSeq) {
            file << val << " ";
        }
        file << endl;
        file.close();
        cout << "Sequence saved to " << filename << endl;
    }

    // Function to visualize the sequence as an ASCII bar chart
    void visualizeSequence() const {
        cout << "\nASCII Representation of Wythoff Sequence:\n";
        for (size_t i = 0; i < lowerSeq.size(); ++i) {
            cout << setw(3) << i + 1 << ": ";
            for (int j = 0; j < lowerSeq[i]; ++j) {
                cout << "*";
            }
            cout << " (" << lowerSeq[i] << ")\n";
        }
    }
};

// Function to display menu options
void displayMenu() {
    cout << "\n===== Wythoff Sequence Generator =====\n";
    cout << "1. Generate & Display Sequence\n";
    cout << "2. Search for a Number in the Sequence\n";
    cout << "3. Save Sequence to a File\n";
    cout << "4. Visualize Sequence\n";
    cout << "5. Exit\n";
    cout << "======================================\n";
}

int main() {
    int choice, N;
    cout << "Enter the number of terms for Wythoff sequence: ";
    cin >> N;

    WythoffSequence wythoff(N);

    while (true) {
        displayMenu();
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
            case 1:
                wythoff.displaySequences();
                break;
            case 2: {
                int searchVal;
                cout << "Enter number to search: ";
                cin >> searchVal;
                if (wythoff.searchElement(searchVal)) {
                    cout << searchVal << " is in the sequence.\n";
                } else {
                    cout << searchVal << " is NOT in the sequence.\n";
                }
                break;
            }
            case 3:
                wythoff.saveToFile("wythoff_sequence.txt");
                break;
            case 4:
                wythoff.visualizeSequence();
                break;
            case 5:
                cout << "Exiting program...\n";
                return 0;
            default:
                cout << "Invalid choice! Please enter a valid option.\n";
        }
    }

    return 0;
}   

输出

 
Enter the number of terms for Wythoff sequence: 30

Sequence generated in 6 ms.

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 1

Wythoff sequence (first 30 terms):
Lower Sequence: 4 19 1 40 3 45 6 8 9 11 12 46 48 14 16 17 21 22 24 25 27 29 30 32 33 35 37 38 42 43 
Upper Sequence: 7 31 2 65 5 73 10 13 15 18 20 75 78 23 26 28 34 36 39 41 44 47 49 52 54 57 60 62 68 70 

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 2
Enter number to search: 39
39 is in the sequence.

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 2
Enter number to search: 43
43 is in the sequence.

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 2
Enter number to search: 1000
1000 is NOT in the sequence.

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 3
Sequence saved to wythoff_sequence.txt

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 4

ASCII Representation of Wythoff Sequence:
  1: **** (4)
  2: ******************* (19)
  3: * (1)
  4: **************************************** (40)
  5: *** (3)
  6: ********************************************* (45)
  7: ****** (6)
  8: ******** (8)
  9: ********* (9)
 10: *********** (11)
 11: ************ (12)
 12: ********************************************** (46)
 13: ************************************************ (48)
 14: ************** (14)
 15: **************** (16)
 16: ***************** (17)
 17: ********************* (21)
 18: ********************** (22)
 19: ************************ (24)
 20: ************************* (25)
 21: *************************** (27)
 22: ***************************** (29)
 23: ****************************** (30)
 24: ******************************** (32)
 25: ********************************* (33)
 26: *********************************** (35)
 27: ************************************* (37)
 28: ************************************** (38)
 29: ****************************************** (42)
 30: ******************************************* (43)

===== Wythoff Sequence Generator =====
1. Generate & Display Sequence
2. Search for a Number in the Sequence
3. Save Sequence to a File
4. Visualize Sequence
5. Exit
======================================
Enter your choice: 5
Exiting program...

结论

总之，Wythoff 序列优雅地阐释了数论和组合数学之间的相互作用。通过利用黄金比例，可以创建具有实际应用的特殊序列。此处提供的 C++ 实现有效地计算了序列，使得试验不同的 N 值变得容易。

下一主题判断数组是否形成山谷 - C++

C++ 中的维思序列

引言

问题陈述

数学背景

示例 1

代码解释

示例 2

Wythoff 序列的应用

示例 3

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的维思序列

引言

问题陈述

数学背景

示例 1

代码解释

示例 2

Wythoff 序列的应用

示例 3

结论

相关帖子

C++ 中如何将整个 ASCII 文件读入 std::string？

C++ 中的弹跳数字

C++ 程序实现中心九边形数

C++ std::launder

C++ basic_istream--unget()

C++ 中的格朗迪数

C++ 检查可能的二分图

在 C++ 中交换不同容器的子范围

C++ 中的 std::exponential_distribution

C++ 中的 std::to_address

订阅 Tpoint Tech