Skip to content

13004: 【原3004】IEEE课程通知

题目

题目描述

author: sjtu_pigoneand 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3004

小学期安排

期末成绩计算:平时作业70% + 两次考试分别15%。 第一次考试满分300分。第二次考试满分按照230分计。 最后祝大家暑假愉快;)

7月9号安排:http://en.wikipedia.org/wiki/Eight_queens_puzzle 回溯搜索 7月6号安排:http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

戎术讲解背包问题,相关动态规划问题。pigoneand讲解动态规划问题和深度优先搜索。 oj题目:1073

蛇形矩阵5行标程

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int n = 5;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j)
            if (i + j <= n + 1) cout << (i + j - 1) * (i + j - 2) / 2 + i * ((i + j) % 2) + j * (1 - (i + j) % 2) << "\t";
            else cout << n * n + 1 - (n - i + n - j + 1) * (n - i + n - j) / 2 - (n - i + 1) * ((i + j) % 2) - (n - j + 1) * (1 - (i + j) % 2) << "\t";
        cout << endl;
    }
}

7月4号安排:张羽兮讲高精度。今天大作业:实现一个高精度类,支持整数的加减乘除,重载+, -, *, /。实现正负数。 构造函数(支持从字符串构造),拷贝构造函数,赋值,重载==,>,<,>=, <=。扩展支持,乘方等其他运算。本周末之前完成。

7月2号安排:戎术介绍testing。pigoneand 介绍 http://www.mochima.com/tutorials/strings.html 布置第一次大作业

implement a c++ string class, support following function: overload operator : +, [], ==, =, etc... io: <<, >> function: find, rfind, find_first_of, find_first_not_of, substr, erase, replace, find_last_of, find_last_not_of unittest: design basic test case

6月29号安排 pigoneand 讲 http://www.cs.princeton.edu/~wayne/kleinberg-tardos/05divide-and-conquer.pdf

高脊同学负责他的题目。

Windning的玩具标程 https://gist.github.com/3002558

分糖果标程 https://gist.github.com/3002563

6月27号安排:袁涛、黄一峰负责两道题。下午负责挑选同学讲题,在下午四点之后公布两位助教的标程供同学参考学习。 课后作业:参考黄一峰的代码实现基于模版的数据结构堆。 实现一个最小堆,支持push, pop, top, empty, clear, size基本操作。 并与STL的priority_queue进行性能比较。截止日期:6月29号

6月25号安排:蔡树阳负责两道题。 pigoneand讲testing, sorting,templates in C++.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-096-introduction-to-c-january-iap-2011/lecture-notes/MIT6_096IAP11_lec09.pdf

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-096-introduction-to-c-january-iap-2011/lecture-notes/MIT6_096IAP11_lec10.pdf

6月20号安排:王凯南负责今天助教工作。上午由他负责布置作业。下午挑选部分同学讲题。 今天oj题目:3013,3014。 另外布置翁老师上次考试的第二题作为课后作业:

2.设计并实现一个保存和处理大规模整型数组的类。该数组中约有1%的非0元素。为了节约存储空间,用一个基于线性探测法的闭散列表存储所有非零元素,所有不在散列表中的元素值被视为0。


1.用单循环链表实现的队列类定义如下,请实现所有的成员函数。

class cycQueue {
    struct Node {
        int data;    // 队列元素
        Node *next;
    };
    Node  *tail;    // 指向队尾元素的指针
    public:
    cycQueue();
    ~cycQueue();
    void enQueue(int x);
    int deQueue();
    bool isEmpty();
};

材料: http://acm.sjtu.edu.cn/courses/cs110/fa11 c++经典教材:C++ Primer (google搜索可以下到电子版)

前两周进行专题训练,早上由负责助教布置题目,讲解知识点。然后开始做题。 下午由助教挑选部分同学讲题,最后由助教(出题人)讲解标程。 同时每周一安排几个专题讲座,讲解coding style, pointer in C, debugging, testing。 后两周布置两个大作业。考试方式待定,但最终成绩主要依赖于平时作业。

6月18号安排:上午-翁老师讲题 pigoneand讲coding style, pointer in C。下午做翁老师考试题目,循环链表 题目描述稍后给出

单链表补充材料:http://blog.csdn.net/hairetz/article/details/5836986 有兴趣同学可以读读研究。 指针与缓冲区溢出 http://baike.baidu.com/view/36638.htm 很有意思的补充材料,看不懂下次讲

上机期末考试通知

本次考试四道题(3009,3010,3011,3012),每题满分100分。总分400分。330分以上即为满分。

感谢大家对我们助教工作的支持。祝大家取得好成绩,千万不要作弊! 否则后果自负。

最后请班级助教汇总你负责的同学的所有平时作业成绩,在下周末之前发给我们以便统计成绩。

第三次上机考试通知

这里通知一下。基于大家的提议,我们第三次上机考(最后一次上机考)定于15周(下周三)老时间地点进行。 麻烦大家通知其他同学,下周三一定要来参加考试。

考试范围为基本数据机构:链表、二叉树、队列、图。 涉及到的算法有:排序,二叉树遍历,图的拓扑排序。 考试题目初定为四道。两道和数据结构有关,一道送分,一道考编程基本能力。

本周上机作业1042,1043

期末之前的实验作业:

请大家在16周周三之前完成以下两个实验并撰写报告。发给对应的助教。

一、  实验名称:排序
二、  实验目的:掌握各种排序算法及运行时间
三、  实验内容:
1、  实现直接选择排序、气泡排序、快速排序和堆排序算法。
2、  重复10次下列工作:
(1) 随机产生50000个1 - 50000之间不同的随机数
(2) 用上述四种算法对他们进行排序
(3) 记录排序的时间
3、  检查运行时间是否符合相应算法的时间复杂度
四、  评分标准
(1) 正确实现四种排序(60分);
(2) 随机产生测试数据(10分);
(3) 记录运行时间(10分);
(4) 有注释,代码易于阅读(10分)
(5) 实验报告撰写认真(10分)。

一、  实验名称:拓扑排序
二、  实验目的:掌握图的存储及拓扑排序算法
三、  实验内容:
给出某专业所有课程及课程之间的先导和后继关系,假设所有课程在每学期都能提供学生选修,学生每学期最多只能选6门课,请为学生安排一个培养计划,使之能用最少的学期数修完所有课程。
不能用STL。
输入规范:
第一行:N,M 。N为课程总数,M为课程关系总数。 课程编号为1..N。
下面M行:每行两个整数a,b。表示a是b的前导课程。 
输出规范:
第一行是最小学期数K
以下K行分别是每个学期所修课程。 如果有多种课程安排方式,取字典序最小的。 
四、  评分标准
(1) 正确选择并实现图的存储及基本运算的实现(30分);
(2) 正确实现队列类(20分);
(3) 正确安排培养计划(30分);
(4) 有注释,代码易于阅读(10分)
(5) 实验报告撰写认真(10分)。

本周作业 1039 1040 以及上次考试的四道题。

上周的作业,关于表达式的计算,可延期到本周五之前交给对应助教。 实验报告的基本要求:说明实现的基本数据结构和思路。 有测试用例,测试程序的正确性。 有程序运行效率的测试(这点不要求每个同学都有)。

第二次上机考解题报告

  1. Windning's Ant 智力题, 因为所有蚂蚁的速度相同, 所以相遇转向的规则可以无视. 统计每只蚂蚁行动到目标端点的时间取最大值即可.

  2. Divisor Summation 本题数据范围较小, 使用暴力方法即可通过. 核心代码:

    for (int i = 1; i < n; ++i) if (n % i == 0) ans += i;

不过本题中的m可以出到200000以上. 有兴趣的同学可以做一下: http://www.spoj.pl/problems/DIVSUM/

  1. Maple Tree 本题主要考察对于二叉树数据结构中递归关系的理解. 由中序加上前序后序中的任意一个遍历, 即可推出另外一个. 主要思路是, 在任意一种遍历中, 一棵子树得到的遍历串一定是一个连续的子串. 如果得到了当前子树的前序子串和中序子串, 由前序子串可知当前子树的根节点, 由中序子串中根节点的位置可知左右子树的子串长度. 然后递归处理左右子树.

核心代码:

// 调用traversal(0, (int)preOrd.size() - 1, 0, (int)postOrd.size() - 1)进入递归
void traversal(int preL, int preR, int inL, int inR)
{
    if (preR - preL + 1 <= 0)
    {
        return ;
    }
    char c = preOrd[preL]; // 根节点
    int inMid = posMap[c]; // posMap[c]为c在中序遍历串中的位置
    int lenL = inMid - inL; // 左子树大小
    traversal(preL + 1, preL + lenL, inL, inMid - 1); // 递归处理左子树
    traversal(preL + lenL + 1, preR, inMid + 1, inR); // 递归处理右子树
    postOrd += c;
}
  1. Maze 主要队列数据结构的主要应用--广度优先搜索. 搜索过程中每次扩展只走一步, 队列先进先出的性质即保证了使用最少的步数走到目标节点. 题目中桥的设定容易干扰思路, 但只要理清思路, 写一个小函数专门判断也很难出错. 这也说明了结构化程序设计的重要.

核心代码:

struct SearchNode
{
    int x, y;
    int step;
    SearchNode(int x, int y, int step)
    {
        this->x = x;
        this->y = y;
        this->step = step;
    }
};

// 常数数组, 方便枚举4个方向的行动方式
int gox[4] = {0, -1, 0, 1};
int goy[4] = {-1, 0, 1, 0};
char gotype[4] = {'-', '|', '-', '|'};

// src 当前所处位置的地形, dst 尝试要走的位置的地形, type 移动类型(横向或纵向)
bool checkMove(char src, char dst, char type)
{
    // ...
}

// 返回值为答案: 最短距离
int work()
{
    // ...
    // 省略了初始化以及边界判断

    queue<SearchNode> que;
    que.push(SearchNode(x1, y1, 0));
    vd[x1][y1] = true; // vd为标记数组, 已经走过的点不会被再次访问, 保证了时间复杂度
    while (!que.empty())
    {
        SearchNode a = que.front();
        que.pop();
        for (int k=0; k<4; k++)
        {
            int bx = a.x + gox[k];
            int by = a.y + goy[k];
            int bstep = a.step + 1;
            if (!vd[bx][by] && checkMove(g[a.x][a.y], g[bx][by], gotype[k]))
            {
                if (bx == x2 && by == y2)
                {
                    return bstep;
                }
                que.push(SearchNode(bx, by, bstep));
                vd[bx][by] = true;
            }
        }
    }
    return -1;
}

第二次上机考试说明

题目错误说明: 3005 输出部分: 输出仅有一行 一个实数,保留3位小数,表示最后一只蚂蚁走下长棍的时刻(s) 提示,可用 printf("%.3f\n", ans); 来输出 %.3f后面是"斜杠,左上角到右下角的斜杠"n 不是 n 使用printf需要

#include <cstdio>
printf("%.3f\n", ans);

3008 n, m <= 100

本次考试一共四道题,每道题满分100分总计400分。时间为两个小时。 考试满分按330分计(即如果你的分数超过330分此次考试成绩就视为满分,以此类推) 考试规则和上次一致,不再赘述。 不允许使用小号交题(实际上也根本不需要) 题目可以反复提交,以最高分计。不允许恶意提交,刷屏等行为。

本周作业 实验10 实验指导书

一、 实验名称:表达式计算

二、 实验目的:掌握二叉树的各种操作

三、 实验内容: 一个算术表达式可以表示成一棵二叉树。对这棵二叉树进行后序遍历,访问到一个运算符时,对它的左右儿子执行相应的运算。当访问到根结点时,得到了整个表达式的运算结果。设计一个能够完成整型数的加、减、乘、除和乘方运算的计算器。其中,乘方的优先级最高,乘除次之,加减最低,可以用小括号改变优先级。乘方是右结合的,其他运算符都是左结合的。所有运算符都是二元运算符,不考虑一元的减法。

四、 评分标准 (1) 正确将表达式转化成表达式树(30分); (2) 考虑了非法表达式的检测(10分); (3) 正确计算表达式的结果(20分); (4) 类的设计正确、合理(10分) (5) 正确设计计算器的控制流程(10分) (6) 有注释,代码易于阅读(10分) (7) 实验报告撰写认真(10分)。

本周作业 1048 1989(选做) 2000 2001

下周第二次上机考。考试时间地点方式方法不变。题目3-4题。 考二叉树之前的内容(包括二叉树)。 题目大致为一道简单题。一或二道数据结构题,一道综合题。每到题目都会有送分的部分。

1051 题解

STL 方法

// Problem 1051
// Created by Chris on 2012.4.11
#include <list>
#include <iostream>
using namespace std;

int main()
{
    list<int> num;
    list<int>::iterator it;
    int n, m, i, tmp, ans = 0;
    cin >> n;
    for (i = 0; i < n; ++i)
    {
        cin >> tmp;
        num.push_back(tmp);
    }
    cin >> m;
    for (i = 0; i < m; ++i)
    {
        cin >> tmp;
        for (it = num.begin(); it != num.end(); ++it)
        {
            ++ans;
            if (*it == tmp)
            {
                num.erase(it);
                num.push_front(tmp);
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

另外一种解法为手写单链表或者双向链表。

//Owner: 5110309069
#include<iostream>
using namespace std;
int main()
{
    struct node
    {
        int v;
        node *h;
    };
    int n;
    cin>>n;
    node *head,*tail;
    head=new node;
    cin>>head->v;
    tail=head;
    for(int i=1;i<n;++i)
    {
        int tmp;
        cin>>tmp;
        node *p;
        p=new node;
        p->v=tmp;
        p->h=NULL;
        tail->h=p;
        tail=p;
    }
    int m;
    cin>>m;
    int cnt=0;
    for(int i=0;i<m;++i)
    {
        int tmp;
        cin>>tmp;
        node *p,*q;
        p=head;
        q=NULL;
        while ((p->v!=tmp)&&(p->h!=NULL))
        {
            ++cnt;
            q=p;
            p=p->h;
        }
        ++cnt;
        if ((q!=NULL)&&(p->v==tmp))
        {
            q->h=p->h;
            p->h=head;
            head=p;
        }
    }
    cout<<cnt;
    return 0;
}

解题报告

1. 二哥的幸运

本题的考察点是循环语句的使用, 旨在送分. 可惜仍有同学没有拿到满分. 我看了下大家的代码, 没有拿到满分的同学大多纠结在int类型和string类型的转换中. 事实上对于int类型只要使用除10模10的循环就可以得到每一位的数字, 没有必要转为string.

while (n != 0)
{
    int digit = n % 10;
    n /= 10;
}

int类型转为string类型也是常见的操作, 如果一定想实现的话, 这里介绍一个技巧, 利用C++ STL的stringstream可以简单的实现:

string intToString(int n)
{
    stringstream ss;
    ss << n;
    string s;
    ss >> s;
    return s;
}

对于其他的类型转换(如string转int)也同理, stringstream具体可参考C++ reference: http://www.cplusplus.com/reference/iostream/stringstream/ 目前阶段机试中并没有禁用STL, 适当利用STL可以节约很多时间.

关于STL: 个人建议有能力的同学要掌握STL的使用(推荐C++ Primer这本书), 节约代码是一方面, 其中代码功能的模块化和代码结构的设计思想更加值得初学者学习. 不过今后视情况可能会在考试中禁用STL(特别是数据结构部分), 所以基本功不够扎实的同学还是应该以夯实基础为主. 考试中不会出现STL特别占优势的题目.

2. Ruko Sort

排序+去重是个经典问题, 传统做法为快速排序之后加上O(n)的扫描, 总时间复杂度O(nlogn), 非本题标准解法不再赘述. 这题的特殊之处在于Ai的范围很小1 <= Ai <= 1000, 我们可以采取更简单的解法. 开一个长度为1000的bool数组(bool flag[1001]), 初始化为false. 然后每读入一个数字就把对应的flag设为true, 输出时只需要统计数组中有多少个true, 然后把数组中对应true的下标输出即可. 时间复杂度为O(m), m是Ai的范围.

另附STL解法(核心部分):

vector<int> data;
void work()
{
    sort(data.begin(), data.end());
    data.resize(unique(data.begin(), data.end()) - data.begin());
    cout << data.size() << endl;
    for (int i = 0; i < (int)data.size() - 1; i++)
        cout << data[i] << " ";
    cout << data[data.size()-1] << endl;
}

3. Strange Mushroom

这道题的主要考点是高精度, 希望大家在作业完成之后能够加以思考, 今后能够熟练的解决同类问题. 因为是防退场题, 所以题目本身出的比较难, 不过考虑到这是第一次考试所以出了大量的送分点, 我们期望的是大部分同学能拿到90分. 可惜很多同学满足于long long能过80%的方法而没有进一步努力. 在此表扬考场中拿到90分的同学, 可惜前面数据放水太多导致这位同学的付出回报不大.

首先根据题目描述可以得到简单的递推方法:

f[i][j]表示第i天长度为j的蘑菇有多少个, 则

f[i][j] =  f[i-1][j-1] + f[i-1][j+1] , when j >= 2

           f[i-1][j+1]               , otherwise

但是因为答案增长较快, 其中的加法需要使用高精度实现, 时间复杂度大致为O(n^2*log(Answer)), 在大数据点上会超时.

如果把f[i][j]列成表格.

+----------+-+-+-+-+-+-+-+
|Day\Length|1|2|3|4|5|6|7|
+----------+-+-+-+-+-+-+-+
|   1      | |1| | | | | |
+----------+-+-+-+-+-+-+-+
|   2      |1| |1| | | | |
+----------+-+-+-+-+-+-+-+
|   3      | |2| |1| | | |
+----------+-+-+-+-+-+-+-+
|   4      |2| |3| |1| | |
+----------+-+-+-+-+-+-+-+
|   5      | |5| |4| |1| |
+----------+-+-+-+-+-+-+-+
|   6      |5| |9| |5| |1|
+----------+-+-+-+-+-+-+-+

可以发现这和杨辉三角相似, 如果从三角形的顶点开始走, 每次只能向左下或右下, 那每个格子上的数就是从顶点到这里的路径数, 如果用-1表示向左下, 1表示向右下, 题目就可以转化为更清晰的形式: 求有多少个长度为n的1 -1序列, 满足任意前k个数的和不小于0. 对于长度为n的1 -1序列, 若包含m个-1, 则共有C(n, m)种排列方式. 其中就有C(n, m-1)个是不合法的, 原因如下: 假设个序列为d1 d2 d3... dn, 如果它不合法, 我们一定可以找到最小的一个k, 使得d1+d2+…+dk = -1 显然其中包含[k/2]个1和[k/2]+1个-1(记[]为取下整, 下同). 对前k个数取反, 就得到了一个包含着m-1个-1的长度为n的序列. 任何一个包含着m-1个-1的序列也可以通过类似的方式转化为包含m个-1的不合法序列, 并且这个转化是一一对应的. 所以上述猜想成立.

我们要求的答案就是

C(n, 0)+C(n, 1)-C(n, 0)+C(n, 2)-C(n, 1)+…+C(n, [n/2])-C(n, [n/2]-1)

= C(n,[n/2])

至此,本题转化成了简单的高精度计算,O(n*log(Answer))即可解决. 实现的时候可以乘除同时进行, 可以大量节省时间空间.

附核心代码:

int n;
BigInt ans;
cin >> n;
ans = 1; // 运算符等号重载, 将int类型转为BigInt类型.
int a, b;
a = n - (n/2) + 1;
b = 1;
for (int i=1; i<=(n/2); i++)
{
    ans.multiplySmall(a); // 高精度整数乘以低精度整数
    ans.divideSmall(b); // 高精度整数除以低精度整数
    a++;
    b++;
}
ans.print();

高精度乘除低精度很好写, 都是一个for循环就能解决的问题, 希望大家能够尝试一下并实现自己的BigInt类:)

翁老师作业6

注意

这道题不需要提交。 我们仅用这道题作为通知各位同学的手段。这样方便我们今后公布解题报告和标准程序等信息。

下周交作业

由于上次通知不及时,请下周三之前大家把翁老师的作业2交给对应的班级助教。 下周五之前,完成翁老师作业6,交给助教。 翁老师作业6的要求实现一些类和对应的操作,由于题目只描述了一个大概, 以下文字仅仅是一个实现参考,我们推荐大家用这些类名和方法名来实现这个作业。 当然大家可以有自己的创造性。在提交作业时,需要注意:

1、代码可读性,要有必要注释 2、较为详细的测试程序 3、体现面向对象的思想

请班级助教按照这三个指标来打分。谢谢

Description

这是翁老师布置作业的第六道题,

实验六 实验指导书

一、 实验名称:银行账户模拟

二、 实验目的:这道题主要目的是加深同对于面向对象编程中继承理解

三、 实验内容: 题目描述:创建一个银行帐户的继承层次,表示银行的所有客户。所有的客户都能在他们的银行帐户中存钱、取钱。任务主要如下: (1) 创建Account类,作为基类。Account类应该包含帐户余额,并提供构造函数;向账户中余额加钱的方法;减少账户中余额的方法;获取当前帐户余额的方法。

Class Account
{
    int saveMoney(double); // success:return 0;  Fail: return -1;
    int takeMoney(double);
    double check();
};

(2) 创建Account类的派生类:储蓄账户SavingAccount类,除去基类Account的所有功能外,储蓄账户还应该具有新的特性。储蓄帐户应该提供一个计算利息的成员函数和将利息加到帐户余额上的操作。

Class SavingAccount
{
    savingAccount(double interestPerYear);
    double calInterest(int year);
    int addInterest(int year);
};

(3) 创建Account类的派生类:支票帐户CheckingAccount类,与储蓄账户不同的是,它没有利率的计算,但是它会在每笔交易后收取一定的交易费用。它需要重新定义基类Account中的成员函数,当每笔交易完成时,在帐户余额中减去交易金额。

Class CheckingAccount
{
    checkingAccount(double percentage);
Override:
    int saveMoney(double); 
    int takeMoney(double);
};

(4) 提示:在提供上述方法时应该注意出错情况的处理,比如帐户余额不足等情况。

四、 程序的输入输出和测试程序 在当这个层次中的类定义完毕后,编写一个程序,要求创建每个类的对象并测试它们的成员函数,并且输出预期的,正确的结果。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!