文章

【软件工程基础】结对项目|四则运算

1.Github链接 https://github.com/FattyHappy/calculator

2.项目预估时间

 

 

 

 

 

 

3.项目实际实现时间

 

 

 

 

 

 

4.项目描述

4.1 需求分析

1. 功能需求 软件的功能需求分为三个部分。
支持一次性生成不超过 1000 道四则运算题目(包含括号),一个表达式中运算符个 数不会超过 10 个。要求所有题目都是合法的四则运算题,并且它们两两都不同构。
要求支持分数表示。 程序应当能接受用户输入的答案,并且判定对错。最后输出正确/错误题数与正确 率。
围绕上述功能,添加一个额外的运算符——乘方,可以用^或**两种表示方法。用 户应当可以自行设置采用何种表示。 应当注意乘方是从右往左计算的,即 2^3^3=2^27= 134217728。

         实现基本功能的命令行程序,并在此基础上添加了附加内容用户可以设置题目范围(多少个数字,用哪些运算符,要出多少题目),同时可以计算有多少题目正确和错误。也可以做普通计算器使用(注意:!!答题格式请严格按照readme里的格式要求!)

start 10:开始 生成10个式子
exit/quit:退出
help:查看帮助
setting:查看当前设置
setpower 0:设置乘方显示参数为0
setopnum 10:设置式子中的运算符数为10
answer 123:提交当前题目的答案为123

calc 2^(-3)**2:计算想要求解式子的值

 

 

2. 性能需求 运行时间限制:一分钟。空间限制:1GB。
3. 结构化需求分析与建模

    a. 数据建模

     实体有原表达式、转换生成的后缀表达式、进一步处理建出的判定树、表达式 的计算结果、用户输入的结果值。 考虑括号的问题,原表达式与后缀表达式应该是多对一的关系。 判定树是必须的,因为表达式同构的问题可以转化成判定树同构的问题。

       

b.功能建模

                  c.行为建模

4.2 算法描述

这里着重讲述我们判定树的生成,我们生成一个式子,在生成后缀表达式的同时就建立出判定树。把把字符栈S2和数字栈S1替换成两个节点栈,然后和后缀表达式求法一样处理。退栈时把S2.top的左右儿子设置为S1的前两个,并把S2.top()扔到S1中视为数字,最后S1剩下的唯一一个节点就是根,否则一定是异常。S2应当维护成一个优先级单调不减的栈,但考虑到乘方计算顺序从右往左,那么乘方采用单调递增维护方式。具体代码请查看源码中 solve函数

4.3 项目思路变更

一开始我们想用c++完成核心代码,然后用js调用,完成第三部分。结果发现太过艰难。

接着我们想用js调用exe,在本地读取exe生成的文档,前端的主界面已基本完成,但由于安全性和兼容性的问题,该方法实现起来也十分困难,

此时,我们项目的时间已经耗费了很多,转而开发其他的项目已经不太现实了。我们决定在命令行里充实我们的程序并且选取最后一个用动画介绍后缀表达式的生成。

4.4 项目演示

首先进入主界面,可以进行选择,如有不明白的,可以查看help

接下来设置一下我们所需要的乘方形式 和 所需要的操作符数

意为只可显示^做操作符,有五个操作符,详细请输入setting查看

接下来start 2,代表出两道题

我们可以看到必须要严格按照答题格式answer+答案

做完后会计算正确率

而且在做题的过程中可以随时更改设置,非常人性化。

并且还支持本身的计算功能,两种次方都可以

4.5 项目测试记录

1.环境的适配,该程序最开始只兼容VS和mingw,在ubuntu下无法运行

解决:加入判定,判断有没有宏定义GNUC

2.setpower修改不起作用

3.setopnum修改不会改变接下来式子符号数的问题

4.answer后面带一个有空格的式子无法识别

以上问题都是在不断测试中发现的,现在都已解决。

 

5.项目反思

在本次项目中,我们在命令行程序实现该项目完成度较高,并且能有不错的创新和较为人性化的设计。只是在项目开始前对于技术的评估和研究不够,导致浪费了很多时间。也体会到了一个简易的较为完整的项目的具体实现。希望自己能不断进步,

 

 

 

 

【软件工程基础】个人项目报告|数独终局生成及解决

【github链接】https://github.com/trrrrafarga/Sudoku

PSP表格

2.解题思路描述

(1)生成数独终局

看到这个题目首先想到暴力做,但是看到题目要求在1s内输出1e6个终局,很明显,如果不进行优化,直接的暴力输出是无法达到的。

接下来的思考,先生成一个数独终局,然后在该终局的基础上进行一些替换操作。在这里,我走了一些弯路,我想的是随机进行调换,然后判断其是否能够满足数独终局判断条件。首先这样可能会出现一些重复(即使是概率渺小)而且每一次都要判断增加了程序的运行时间。

我认为数独的第一行是至关重要的,在确定了第一个位置只能是8之后,还有八个数字可以选择。那么第一行就会有8!种可能(也就是40320种)。看数独是一个9*9的矩阵,那么会不会有什么规律能够根据第一行的变换生成一个终局。于是我查阅了一些资料。发现可以把第一行向右平移一定的位数,只要每一行平移的次数和之前的任意一行不一样,那么每一列也不会有重复的数字。接下来,考虑九宫格的不重复问题,我们只需要将每三行看成一组,组内向右移动都移动相差3的倍数个单位时就可以保证每宫内没有重复的数字。

通过这样的方法,我们不仅可以生成不重复的数独终局,而且省去了判断是否为数独终局这样一个很耗时的部分。由于第一行的第一个数字不能动,那么第一行只能平移0行,第二三行都可平移3或6个单位,我们记为036和063,456行的平移就很随意了,我们可以选择1,4,7三个数字自由组合就有了6种,789行选择2,5,8又有了6种,此时,对于每一个第一行排列就会有72种了,那么40320*720可比1e6要大惹。

(2)解决数独

解决数独我们就用了最经典的回溯法解决问题。

填充空缺,然后判断,如果可以就继续,如果不行就往回走。直到解决问题。

3.设计实现过程

本次实现采用C++语言

在主函数里,根据所输入的指令,看所需要实施的是哪类问题。整个问题总共设置了7个函数,除去主函数外,buildMove(int N)(利用全排列生成初始终局)BuildSudoku(char *rule1,char *rule2, char*rule3)(根据不同规则变化终局)print1()(输出终局)这三个解决数独终局问题,然后judge,move,change三个函数解决数独求解问题。

5.性能展示

为了改进性能,首先是更改了生成数独终局的方法,使其变得更加直接。在解决的时候加入了剪枝等操作,那么接下来就是性能分析图

我们可以看出在改变方法之后,输出1e6个终局耗费最多的是输出部分。

 

6.代码说明

生成数独终局中最关键的就是调换和全排列生成。

这里的规则rule就是我们之前说的036,147之类的交换规则。

我们先把除了8之外的数字加入一个数组生成全排列,然后根据思路里的规律来进行变换

解决问题时,就是一个回溯算法,比较关键的是判断时要考虑九宫格的问题,在搜索资料的时候找到了一个比较好的办法。

7.实际表格

 

 

 

 

 

惶想录:101 10000

进入计算机这个专业已经快两年了,我虽然不是一个优秀的CSer,但是一直对算法保持着敬仰的态度。觉得算法是提高人生活质量最重要的东西,算法复杂度的降低,就意味着人类的进步。

当然,这是我冷静下来思考的结果。

在遇到很难看懂的算法的时候,我真的很希望他就在纸上爆炸。

但是随着算法的进化(也不能叫进化,是人被钱财昧了良心啊!),有些事情开始变得可怕了。四月中旬我在淘宝上订了妇联3的票,之后我的哔哩哔哩首页上竟然大多都是看妇联3你需要知道的XXX。我最开始也并没有觉得有什么,但是当我发现首页上还有我手机里下的一些游戏相关的视频时,我觉得事情变得有些奇妙了,更奇妙的是,还有我购物车里相关商品的视频。或许设计他的人觉得这样很人性化,但是让人浑身不舒服,各种APP的交易明目张胆,就像是寄生在手机里的偷窥者更加明目张胆地活动起来了。

我之前一点也不在意个人信息泄露,我知道泄露个人信息太简单了,似乎是很廉价的事情,但当这些东西赤裸裸地展现在我面前的时候。我还是会产生微妙的生理不适感。仿佛小偷进入你家在装睡的耳边告诉你:“我知道你没睡着”。前两天寝室里空调可以用了,想着在美团上找个专业的来,但是贫民窟男孩因为一些我们都知道的原因搁置了这个计划。可是巧的是,第二天,我就收到了两个电话,问我需不需要空调上门清洁。我心知肚明地把他看成巧合,当做谈资。在写这篇文章的下午,我的知乎又给我推送了“如何评价某某品牌的鞋子”,而中午我刚刚买了一双。你看,互联网时代多么便利啊。心想事成的时代就要来了。

我们要活在阳光下啊,然后,暴晒而死。

最后,本咸鱼提前给Skip—Gram with negative samping拜个早年!
为我即将换掉的deepin默哀!

BITOJ–木板墙

考古学家在人迹罕至的一块平地上发现了由一堆木板拼成的墙。令人惊奇的是这些木板的宽度都相同!地下的部分都已腐烂,而地上的部分也有高有低,甚至有的地方根本没有木板,所以考古学家决定带走面积最大的长方形回去研究。

输入:
首先是整数n(1<=n<=100000),表示木板的块数。接下来是n个整数h1,…,hn, 其中0<=hi<=1000000000,它们按照从左到右的顺序表示木板的高度。每块木板的宽度都是1。

最后一个0表示程序的结束。
输出:
其中最大长方形的面积。

这道题有三种做法,纯暴力,有技巧的暴力,和 单调栈的方法。

头铁的我,三种方法都试了,当然 纯暴力会TLE。

纯暴力的思想就是把每一个木板都当做最短板,然后依次向左右遍历,看旁边的是不是比他要长。所以复杂度应该是 o(n^2)

有技巧的话,就是用两个数组,分别记录每一个数左边和右边比他大的,这样到第i的时候,我们就可以看看i-1的情况,可以缩短时间
/*展示一下我爱的solarized dark配色!!*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include"cstdio"
#include"iostream"
#include"cstring"
using namespace std;

long long forest[100005];
int map_left[100005];
int map_right[100005];

int main(int argc, char const *argv[])
{
    int n,k;
    long long max;
    while(1)
    {
        max = 0;
        scanf("%d",&amp;n);
        if(n == 0) break;
        else
        {
            for(int i = 1; i &lt;= n; ++i)
            {
                scanf("%lld",&amp;forest[i]);
                map_left[i] = 0;
                map_right[i] = 0;
            }

            for(int i = 2;i &lt;= n;i++) { if(forest[i] &gt; forest[i-1])
                    map_right[i] = 0;
                else
                {
                    k = i-1-map_right[i-1]-1;
                    while(k &gt; 0 &amp;&amp; forest[k] &gt;= forest[i])
                    {
                        k = k - map_right[k] - 1;
                    }
                   
                    map_right[i] = i-k-1;
                }
            }

            for(int i = n-1;i &gt; 0;i--)
            {
                if(forest[i] &gt; forest[i+1])
                    map_left[i] = 0;
               
                else
                {
                    k = i + 1 + map_left[i+1] + 1;
                    while(k &lt;= n &amp;&amp; forest[k] &gt;= forest[i])
                    {
                      k = k + map_left[k] + 1;
                    }
                   
                    map_left[i] = k-i -1;
                }
            }

            for(int i = 1;i &lt;= n;i++) { if((map_left[i] + map_right[i] + 1)*(forest[i]) &gt; max)
                {
                    max = (map_left[i] + map_right[i] + 1)*(forest[i]);
                }
            }

            printf("%lld\n", max);
        }
    }
    return 0;
}

没有高亮就是在耍流氓。

Dream –imagine dragons

In the dark

And I’m right on the middle mark

I’m just in the tier of everything that rides below the surface

And I watch from a distance seventeen
And I’m short of the others dreams of being golden and on top
It’s not what you painted in my head
There’s so much there instead of all the colors that I saw
We all are living in a dream
But life ain’t what it seems
Oh everything’s a mess
And all these sorrows I have seen
They lead me to believe
That everything’s a mess
But I wanna dream
I wanna dream
Leave me to dream
In the eyes
Of a teenage crystallized
Oh the prettiest of lights that hang the hallways of the home
And the cries from the strangers out at night
They don’t keep us up at night
We have the curtains drawn and closed
We all are living in a dream
But life ain’t what it seems
Oh everything’s a mess
And all these sorrows I have seen
They lead me to believe
That everything’s a mess
But I wanna dream
I wanna dream
Leave me to dream
I know all your reasons
To keep me from seeing
Everything is actually a mess
But now I am leaving
All of us were only dreaming
Everything is actually a mess

 

I wanna dream
I wanna dream
Leave me to dream