C++

AI悦创原创2023年5月21日大约 7 分钟...约 2079 字

Section A: Short Questions

A3

a) What is stack memory and heap memory used for?

|----------------|   
 |     ...        |   
 |----------------|   
 |   返回地址     | <- g() 返回到 f() 的地址
 |----------------|   
 |    g 的局部变量 | <- g() 的局部变量 (在这个例子中没有)
 |----------------|   
 |   返回地址     | <- f() 返回到 main() 的地址
 |----------------|   
 |    f 的局部变量 | <- f() 的局部变量 (在这个例子中没有)
 |----------------|   
 |   返回地址     | <- main() 的返回地址 (通常指向系统的退出程序)
 |----------------|   
 |  main 的局部变量 | <- main() 的局部变量 (在这个例子中没有)
 |----------------|

|----------------|   
 |     ...        |   
 |----------------|   
 |   返回地址     | <- f() 返回到 main() 的地址
 |----------------|   
 |    f 的局部变量 | <- f() 的局部变量 (在这个例子中没有)
 |----------------|   
 |   返回地址     | <- main() 的返回地址 (通常指向系统的退出程序)
 |----------------|   
 |  main 的局部变量 | <- main() 的局部变量 (在这个例子中没有)
 |----------------|

我们违反的原则是封装。在面向对象编程中，封装是一种隐藏对象内部细节并通过公共方法访问对象数据的方式。它可以防止外部代码直接访问对象内部的数据，从而可能导致状态不一致或者违反业务逻辑（如矩形的宽度或高度为负数）。直接访问和修改成员变量，会破坏对象的封装性，从而引发错误和不可预测的行为。

// 引入stdio库，该库包含了输入和输出的函数
#include <stdio.h>

// 定义一个名为rectangle的类
class rectangle {
private: // 以下成员变量为私有，不能直接被外部访问
    int width; // 矩形的宽度
    int height; // 矩形的高度

public: // 以下为公开的成员函数，可以被外部访问
    // 设置宽度的函数，参数为整数w
    void setWidth(int w) {
        if(w > 0) { // 如果w大于0
            width = w; // 将w的值赋给width
        } else { // 如果w不大于0
            // 输出错误信息
            printf("Width must be a positive integer.\n");
        }
    }

    // 设置高度的函数，参数为整数h
    void setHeight(int h) {
        if(h > 0) { // 如果h大于0
            height = h; // 将h的值赋给height
        } else { // 如果h不大于0
            // 输出错误信息
            printf("Height must be a positive integer.\n");
        }
    }

    // 获取宽度的函数，返回宽度的值
    int getWidth() {
        return width;
    }

    // 获取高度的函数，返回高度的值
    int getHeight() {
        return height;
    }
};

// 主函数，程序从这里开始执行
int main() {
    rectangle r1; // 创建一个rectangle类型的对象r1
    r1.setWidth(5); // 调用r1的setWidth函数，设置宽度为5
}

// 引入stdio库，该库包含了输入和输出的函数
#include <stdio.h>

// 定义一个名为rectangle的类
class rectangle {
private: // 以下成员变量为私有，不能直接被外部访问
    int width; // 矩形的宽度
    int height; // 矩形的高度

public: // 以下为公开的成员函数，可以被外部访问
    // 设置宽度的函数，参数为整数w
    void setWidth(int w) {
        if(w > 0) { // 如果w大于0
            width = w; // 将w的值赋给width
        } else { // 如果w不大于0
            // 输出错误信息
            printf("Width must be a positive integer.\n");
        }
    }

    // 设置高度的函数，参数为整数h
    void setHeight(int h) {
        if(h > 0) { // 如果h大于0
            height = h; // 将h的值赋给height
        } else { // 如果h不大于0
            // 输出错误信息
            printf("Height must be a positive integer.\n");
        }
    }

    // 获取宽度的函数，返回宽度的值
    int getWidth() {
        return width;
    }

    // 获取高度的函数，返回高度的值
    int getHeight() {
        return height;
    }
};

// 主函数，程序从这里开始执行
int main() {
    rectangle r1; // 创建一个rectangle类型的对象r1
    r1.setWidth(5); // 调用r1的setWidth函数，设置宽度为5
//
}

n <- 5000 # 定义一个变量n，赋值为5000
for (i in 1:n){ # 对于1到n（包括n）的每个数i
    is_square <- F # 创建一个布尔变量is_square，初值为假
    for (j in 1:i){ # 对于1到i（包括i）的每个数j
        if (j*j == i){ # 如果j的平方等于i
            is_square <- T # 那么把is_square设为真
            break # 并退出内层循环
        }
    }
    if (is_square == T){ # 如果is_square为真（说明i是一个平方数）
        print(i) # 那么打印i
    } 
}

大约需要8秒。因为上述程序的时间复杂度大致为O(n^2)。当n从5000增加到10000时，所需的时间将大约为原来的4倍。因此，如果n=5000时需要2秒，那么n=10000时大约需要2*4=8秒。

如果n变为15000，那么根据 $O(n^2)$ 的时间复杂度，计算时间大致会增加到原来的 $(15000/5000)^2 = 3^2 = 9$ 倍。

所以，如果n=5000时需要2秒，那么n=15000时大约需要2*9=18秒

为什么是O(n^2)？

在给出的代码中，我们看到两个嵌套的for循环。外层循环遍历从1到n的每个数字i，内层循环遍历从1到i的每个数字j。由于i最大可以等于n，因此在最坏的情况下（即当i=n时），内层循环可以执行n次。这意味着每次外层循环执行时，内层循环最多执行n次。由于外层循环执行n次，因此总共的执行次数最多为n * n，即n^2。

所以，这个程序的时间复杂度是O(n^2)。这意味着当n的大小变化时，所需的计算时间会按照n的平方变化。这是由于嵌套循环的结构，每次外层循环都会触发内层循环n次，因此执行次数为n的平方。

如果n变为15000，那么根据 $O(n^2)$ 的时间复杂度，计算时间大致会增加到原来的 $(15000/5000)^2 = 3^2 = 9$ 倍。

所以，如果n=5000时需要2秒，那么n=15000时大约需要2*9=18秒。

如果n变为20000，那么根据 $O(n^2)$ 的时间复杂度，计算时间大致会增加到原来的 $(20000/5000)^2 = 4^2 = 16$ 倍。

所以，如果n=5000时需要2秒，那么n=20000时大约需要2*16=32秒。

在R语言中，for循环的范围包括终点。也就是说，如果你写 for(i in 1:n)，那么循环的最后一次迭代，i的值会等于n。所以，如果n是5000，那么在循环中，i会取到5000。

相比之下，一些其他的编程语言，例如C或者Python，在类似的for循环中，循环的范围是不包括终点的。例如在Python中，for i in range(1, n)，i的最大值会是n-1，而不会取到n。

Write a complete C program which produces the following display output:

*
***
*****
*******
*********

#include <stdio.h>  // 引入标准输入输出库，提供printf等函数

void main()  // 主函数，程序执行的入口
{
    // 外层for循环，i的初始值为0，每次循环后i增加2，直到i小于10为止
    for (int i = 0; i < 10; i += 2) {
        // 内层for循环，j的初始值为0，每次循环后j增加1，直到j小于等于i为止
        for (int j = 0; j <= i; j++) {
            printf("*");  // 打印星号，没有换行，因此这些星号将在同一行打印
        }
        printf("\n");  // 在打印完一行的星号后，打印换行符，使得下一行的星号在新的一行打印
    }
}

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQ

方法二：微信：Jiabcdefh