首页 笔记 计算机科学

  1. 指定一个区间 [x,y] ，在一个存有 n 个整数的顺序表中删除处于该区间之中的数。要求时间复杂度小于 O(n^2) 。

    可以使用划分的算法来进行判断并删除。
    代码如：

    void fun(SqList *L, int x, int y)
    {
        int i = 0, j = L->length - 1;
        while (i < j)
        {
            // while (i < j)
            // {
            //     if (L->data[i] >= x && L->data[i] <= y)
            //     {
            //         break;
            //     }
            //     else
            //     {
            //         i++;
            //     }
            // } // 和下面的 while 等价
            while (i < j && (L->data[i] < x || L->data[i] > y))
            {
                i++; //i 从左向右扫描，遇到在 [x,y] 区间的数停下
            }
            // while (i < j)
            // {
            //     if (L->data[j] < x || L->data[j] > y)
            //     {
            //         break;
            //     }
            //     else
            //     {
            //         j--;
            //     }
            // } // 和下面的 while 等价
            while (i < j && L->data[j] >= x && L->data[j] <= y)
            {
                j--; //j 从右向左扫描，遇到不在 [x,y] 区间的数停下
            }
            swap(*&(L->data[i]), *&(L->data[j]));
        }
        L->length = i;//i 扫描过的数均为不在 [x,y] 区间的数
    }
    也可以直接使用删除的算法。
  2. 给定一个正整数，求和是该正整数的正整数序列。例如：6=1+2+3。
    void fun(int n)
    {
        int a = 0;
        int *s = &a; // 用于取出循环计算结果
        int flag = 0;
        for (int i = n / 2; i > 0; i--) // 从 n/2 开始 i 向下遍历
        {
            for (int c = i, sum = 0; sum < n; ++c) // 从 i 开始 c 向 n 遍历，一旦 sum 大于 n 则跳出循环
            {
                sum = sum + c;
                *s = sum;
            }
            if (*s == n)
            {
                for (int j = i, sum = 0; sum != *s; j++) // 输出正整数序列
                {
                    cout << j << "+";
                    sum = sum + j;
                }
                cout <<char(8) <<"=" << *s << endl;//ASCII 中 8 是 backspace，用于删除循环输出的多余的加号，*s 输出计算结果，即 n
                *s = 0;
                flag += 1;
            }
        }
        if (flag == 0)
        {
         cout << "找不到" << endl;
        }
    }
    由题目可知只要有输出，输出一定是等差数列，且和为nn。所以，考虑等差数列求和公式
    Sn=na1+n(n−1)2dS_n=na_1+\dfrac{n(n-1)}{2}d
    由题，SnS_n 为用户输入，d=1d=1；a1,n∈N+a_1,n\in \N^+。所以，可以将原式转化为含Sn,nS_n,n 的不等式，即
    Snn−n−12=a1≥1(1)\dfrac{S_n}{n}-\dfrac{n-1}{2}=a_1\geq 1\space\space\space (1)
    配方可得nn 有上界，即
    n≤2Sn+14−12n\leq \sqrt{2S_n+\dfrac{1}{4}}-\dfrac{1}{2}
    由此得到nn 的遍历范围。将nn 向下取整后在式（1）中按此范围遍历，验证求得的a1a_1 是否是整数。若是，则直接按a1a_1 和当前的nn 进行输出后继续循环；若否，则直接继续循环。
    如此，算法复杂度为n\sqrt{n}。
    代码如下：
    void fun(int m)
    {
        int n = 0,start = 0,end = 0,flag = 0;
        double temp = 0.0;
        for (n = sqrt(2.0 * double(m) + 0.25) - 0.5; n > 1; --n) 
        {
            temp = double(m) / n - double(n - 1) * 0.5f;
            if (temp == int(temp))
            {
                for (flag = 1,start = int(temp),end = start + n; start < end; start++)
                {
                    cout << start << '+';
                }
                cout << char(8) << endl;
            }
        }
        if (flag == 0)
        {
            cout << "None." << endl;
        }
    }