Homework 1

标★的题目为选做题，仅供学有余力的同学尝试，并且评分标准也更严格。请先做完不标★的题目，再尝试做标一个★的题目，再尝试做更多★的题目。

• Introduction：0+0.4
• 语言基础：6+2.7
• Big O notation：10+0.5
• Complexity：14+0.4

本次作业总分：30+4.0

Introduction

★简答题（0.4分）

1. NOI2018是第几届NOI？ 35
2. IOI2018是第几届IOI？ 30
3. NOIP的全称是什么？ 全国青少年信息学奥林匹克联赛
4. 本次作业的提交方式是？提交的截止时间是？
   email提交，8.4晚23:33之前（qwq）

语言基础

在这些题目中，我们只考虑通常的NOI Linux比赛环境：计算机的字长为32位，有符号整数类型采用补码（2's complement）方法表示。并且，我们暂且不考虑C++标准的要求，只考虑实际编译器的效果。

整数类型（6.2分）

对于下面的整数类型，指出其宽度（以二进制位计）、能表示的最小数、能表示的最大数。并指出类型描述的哪些词可以被省略。

例子：signed int，是整数类型，宽度为32，能表示的最小数为-2147483648，能表示的最大数为2147483647，signed可被省略。
（注：C++标准对此宽度的限制仅为“至少为16”，但通常的实践中都是至少为32，在上述的环境中为32，所以本题中我们先不管C++标准对于宽度的限制）

1. unsigned short int
2. short short int
3. int
4. unsigned int
5. long int signed
6. int long unsigned long
7. ★signed char
8. ★double

★看结果写输入（0.4分）

★(1)

#include <cstdio>
int main()
{
    unsigned int a = 233;
    scanf("%u", &a);
    if(a == -a){
        printf("OK\n");
        return 0;
    }
    else return 1;
}

输入什么会输出OK？请给出两个答案（如果你只能想出一个就写一个），输入中不能有任何空白字符。
0 2147483648

★★(2)

#include <cstdio>
int main()
{
    float a = 2.33;
    scanf("%f", &a);
    if(a != a){
        printf("OK\n");
        return 0;
    }
    else return 1;
}

输入什么会输出OK？请给出两个答案（如果你只能想出一个就写一个），输入中不能有任何空白字符。

★标准函数（2.0分）

你最好能够理解以下每个函数的功能。请简单写下以下每个函数的功能，如果你认为你已经熟练掌握则不必写。

这道题为选做题的原因并不是因为难度，而是题太多了……

<cmath>
sin log atan2 fmod remainder
<cctype>
isdigit
<cstdlib>
atoi strtoul
<cstring>
strcpy strncpy strcat strncat strlen strcmp strncmp strstr
memcmp memset memcpy memmove

★★★这段程序怎么了？（0.1分）

#include <cstdio>
#include <cstring>
#include <ctime>
struct Test
{
    char a; int b; short c;
};
void test()
{
    Test t = {
        .a = 'a', .b = 2333, .c = 666
    };
    Test u =
    {
        .a = 'a', .b = 2333, .c = 666
    };
    if(memcmp(&t, &u, sizeof(Test)) == 0)
        printf("t == u\n");
    else printf("t != u\n");
}
void magic()
{
    int a[6] = {2, 3, 3, 6, 6, 6};
    printf("magic %d\n", a[time(0) % 6]);
}
int main() {
    for(int i = 0; i < 3; i++)
    {
        test();
        magic();
    }
    return 0;
}

在不同的编译器、编译选项下运行都会得到不同的结果，并且会经常出现t != u的输出，这是为什么呢？难道是因为定义t和u的时候一个大括号换行了而另一个没有？？？

我觉得这个magic肯定不是看着玩的……所以大概和它有关233333

Big O notation

选择题（10.5分）

d1. $T(n)=n$
g2. $T(n)=n-n^2+n^3$
b2. $T(n)=\ln n$
b3. $T(n)=\ln(n^2)$
d4. $T(n)=\ln(2^n)$
e5. $T(n)=\ln(n!)$
e6. $T(n)=\ln(n^n)$
i7. $T(n)=n\cdot 2^n$
d8. $T(n)=\ln(n\cdot 2^n)$
d10. $T(n)=\sqrt{n \ln n}$
d9. ★$T(n)=3^{\log_2 n}$
b10. ★$T(1)=1,T(n)=2T(\lfloor n/2 \rfloor)+1$
d10. ★$T(1)=1,T(n)=2T(\lfloor n/2 \rfloor)+n$
e10. ★$T(1)=1,T(n)=2T(\lfloor n/2 \rfloor)+n \ln n$
i10. ★$T(1)=T(2)=1,T(n)=T(n-1)+T(n-2)+1$

可供选择的选项：

A. $O(\log \log n)$

B. $O(\log n)$，但不是A

C. $O(\sqrt n)$，但不是A，也不是B

D. $O(n)$，但不是以上任何选项

E. $O(n \log n)$，但不是以上任何选项

F. $O(n^2)$，但不是以上任何选项

G. $O(n^3)$，但不是以上任何选项

H. $O(n^{\ln n})$，但不是以上任何选项

I. $O(2^n)$，但不是以上任何选项

J. $O(\exp n)$，但不是以上任何选项

K. $O(n!)$，但不是以上任何选项

L. $O(n^n)$，但不是以上任何选项

M. 不是以上任何选项

Complexity

判断复杂度（11.2分）

判断下列代码的时间复杂度。请用大$\Theta$记号，或用你认为最紧的大$O$记号来表示。本题中假定每个变量的取值范围不受计算机字长限制。

(1) O(n^2)

for(i = 1; i <= n; i++)
    for(j = 1; j <= i; j++)
        ans++;

(2) O(n^3)

for(i = 1; i <= n; i++)
    for(j = 1; j <= i; j++)
        for(k = i; k <= n; k++)
            ans++;

(3)O(logn)

for(i = 1; i <= n; i *= 2)
    ans++;

(4)O(nlogn)

for(i = 1; i <= n; i++)
    for(int j = 1; j <= i; j *= 2)
        ans++;

(5)O(lognlogn)

for(i = 1; i <= n; i *= 2)
    for(int j = 1; j <= i; j *= 2)
        ans++;

(6)O(nlogn)

for(i = 1; i <= n; i++)
    for(int j = 1; j <= n; j += i)
        ans++;

(7)O(n)

for(i = 1; i <= n; i *= 2)
    for(int j = 1; j <= n; j += i)
        ans++;

(8)O(2^x)

void f(int x) {
    if(x >= 3) {
        f(x - 1);
        f(x - 2);
        ans++;
    }
}
f(n);

(9)O(x)

void f(int x) {
    if(x >= 2) {
        f(x / 2);
        f(x / 2);
        ans++;
    }
}
f(n);

(10)O(x^2)

void f(int x) {
    if(x >= 2) {
        f(x / 2);
        f(x / 2);
        for(int i = 1; i <= x; i++)
            ans++;
    }
}
f(n);

(11)O(x^2)

void f(int x) {
    if(x >= 2) {
        ans++;
        for(int i = 1; i < x; i++)
            f(i);
    }
}
f(n);

★(12)

void f(int n, string s) {
    ans++;
    if(s.length() < n)
        for(char c = '0'; c < '0' + n; c++)
            if(s.find(c) == string::npos)
                f(n, s + c);
}
f(n, "");

★(13)O(2^x)

void f(x) {
    if(x >= 4) {
        f(x - 1);
        f(x - 3);
        ans++;
    }
}
f(n);

提示：实在判断不准的，可做实验试试。

判断题（3.2分）

对于每道题，回答“对”或“错”或“目前无法确定”。

对1. 如果存在一个NP-完全问题能被确定图灵机在多项式时间内解决，则所有NP问题都能被这样解决。
错2. 任何NP问题都不是P问题。
对3. 存在一个问题，既是NP问题，又是NP-难问题。
错4. ★存在一个问题，既是P问题，又是NP-完全问题。
目前无法确定5. ★如果存在一个NP-难问题能被确定图灵机在多项式时间内解决，则所有NP-完全问题都能被这样解决。