描述

有一个不为空且仅包含正整数的数组,找出其中出现频率最高的前 K 个数,时间复杂度必须在 O(n log n) 以内。

输入

一行数据包括两部分,一个正整数数组(数字间 ‘,’ 分隔)和一个正整数 K (1 ≤ K ≤ 数组长度),数组和 K 之间有一个空格。

输出

输出包含前 K 个出现频率最高的数(出现频率相同时,较小的数在前),用 ‘, ‘ 分隔,保证升序排列。

输入样例

1,1,1,2,2,3 2

输出样例

1,2

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

struct  key_value
{
    int num;
    int cnt;
};

int comp(const key_value &a,const key_value &b)
{
    if(a.cnt == b.cnt)
    {
        return a.num<b.num;
    }
    else
        return a.cnt>b.cnt;
}

int main()
{
    vector<int>a(0);
    int k ;
    int num;
    string s;
    while(cin>>s>>num)
    {
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                a.push_back(b);
            }
        }
        sort(a.begin(),a.end());
        struct key_value book[a.size()+1];
        temp = a[0];
        j = 0;
        for(int i = 0; i<a.size(); i++)
        {
            if(temp == a[i])
            {
                cnt++;
            }
            else
            {
                book[j].num = temp;
                book[j].cnt = cnt;
                j++;
                temp = a[i];
                cnt = 1;
            }
        }
        book[j].num = temp;
        book[j].cnt = cnt;
        j++;
        sort(book,book+j,comp);
        if(num>0)
        {
            for(int i = 0; i<num-1; i++)
            {
                cout<<book[i].num<<",";
            }
            cout<<book[num-1].num<<endl;
        }
    }
}

 

描述

给出一组不重复的正整数,从这组数中找出所有可能的组合使其加合等于一个目标正整数 M,如:

一组数为 1, 2, 3,目标数为 4,那么可能的加合组合为: 1, 1, 1, 1 1, 1, 2 1, 2, 1 1, 3 2, 1, 1 2, 2 3, 1 注意相同的组合数字顺序不同也算一种,所以这个例子的结果是 7 种。

输入

一组连续不重复的 N 个正整数(, 隔开,0<N<100)以及目标正整数(与数组之间用空格隔开)

输出

所有可能的加合等于目标正整数 M 的组合种数

输入样例

1,2,3 4

输出样例

7

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

vector<int>a(0);
int findComb(int k){
    int sum = 0;
    for(int i = 0; i < a.size();i++){
        if(k-a[i] == 0){
            sum++;
            break;
        }
        if(k-a[i]>0){
            sum = sum +findComb(k-a[i]);
        }
        if(k-a[i]<0){
            break;
        }
    }
    return sum;
}


int main()
{
    int k ;
    int num;
    string s;
    while(cin>>s>>num)
    {
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                a.push_back(b);
            }
        }
          sort(a.begin(),a.end());
           cout<<findComb(num)<<endl;
    }
}

 

描述

给定任意一个较短的子串,和另一个较长的字符串,判断短的字符串是否能够由长字符串中的字符组合出来,且长串中的每个字符只能用一次。

输入

一行数据包括一个较短的字符串和一个较长的字符串,用一个空格分隔,如: ab aab bb abc aa cccc uak areuok

输出

如果短的字符串可以由长字符串中的字符组合出来,返回字符串 “true”,否则返回字符串 “false”,注意返回字符串类型而不是布尔型。

输入样例

a b
aa ab
aa aab
uak areuok

输出样例

false
false
true
true

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

string createStr(string str2,string str1)
{
       int a[130];
       string result = "true";
       memset(a,0,sizeof(a));
       for(int i = 0;i<str1.length();i++){
          a[int(str1[i])]++;
       }
       for(int i = 0;i<str2.length();i++){
          a[int(str2[i])]--;
          if(a[int(str2[i])] < 0){
             result =  "false";
          }
       }
       return result;

}

int main()
{
    int k = 0;
    string s1,s2;
    while(cin>>s1>>s2)
    {
         cout<<createStr(s1,s2)<<endl;
    }
}

 

描述

在你面前有一个n阶的楼梯,你一步只能上1阶或2阶。 请问计算出你可以采用多少种不同的方式爬完这个楼梯。

输入

一个正整数,表示这个楼梯一共有多少阶

输出

一个正整数,表示有多少种不同的方式爬完这个楼梯

输入样例

5
10

输出样例

8
89

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;


int climbStairsWays(int num)
{
    int res = 0;
    if(num == 1)
    {
        res = 1;
    }
    else if(num == 2)
    {
        res = 2;
    }
    else if(num == 3)
    {
        res = 3;
    }
    else
    {
        int temp1 = 1;
        int temp2 = 2;
        int temp3 = 3;
        num = num - 3;
        while(num--)
        {
            res = temp2 + temp3;
            temp1 = temp2;
            temp2 = temp3;
            temp3 = res;
        }
    }
    return res;
}

int main()
{
    int k = 0;
    while(cin>>k)
    {
        cout<< climbStairsWays(k)<<endl;
    }
}

 

  • 关于操作系统

1.1 操作系统

操作系统是管理计算机硬件与软件资源的计算机程序,同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。 操作系统的型态非常多样,不同机器安装的操作系统可从简单到复杂,可从手机的嵌入式系统到超级计算机的大型操作系统。许多操作系统制造者对它涵盖范畴的定义也不尽一致,例如有些操作系统集成了图形用户界面,而有些仅使用命令行界面,而将GUI视为一种非必要的应用程序。

1.2 网络操作系统

网络操作系统 ,是一种能代替操作系统的软件程序,是网络的心脏和灵魂,是向网络计算机提供服务的特殊的操作系统。借由网络达到互相传递数据与各种消息,分为服务器(Server)及客户端(Client)。而服务器的主要功能是管理服务器和网络上的各种资源和网络设备的共用,加以统合并控管流量,避免有瘫痪的可能性,而客户端就是有着能接收服务器所传递的数据来运用的功能,好让客户端可以清楚的搜索所需的资源。

  • 网络操作系统概述

2.1 网络操作系统概述

网络操作系统(NOS)是网络的心脏和灵魂,是向网络计算机提供服务的特殊的操作系统。它在计算机操作系统下工作,使计算机操作系统增加了网络操作所需要的能力。网络操作系统严格来说应称为软件平台。网络操作系统运行在称为服务器的计算机上,假如你的PC装了此系统,你的PC就是一个小服务器,并由联网的计算机用户共享,这类用户称为客户。

NOS是以使网络相关特性达到最佳为目的的,如共享数据文件、软件应用,以及共享硬盘、打印机、调制解调器、扫描仪和传真机等。一般计算机的操作系统,如DOS和OS/2等,其目的是让用户与系统及在此操作系统上运行的各种应用之间的交互作用最佳。

NOS已资源共享和信息交换为目的。如你要下载一个mp3,在网络操作系统中,你必须找到它的具体下载地址。

2.2 分布式操作系统概述

分布式操作系统是建立在网络操作系统之上,对用户屏蔽了系统资源的分布而形成的一个逻辑整体系统的操作系统。

2.3 网络操作系统和分布式操作系统的区别

分布性。分布式操作系统的处理和控制功能均为分布式的;而网络操作系统虽具分布处理功能,但其控制功能却是集中在某个或某些主机或网络服务器中,即集中式控制方式。

并行性。分布式操作系统具有任务分配功能,可将多个任务分配到多个处理单元上,使这些任务并行执行,从而加速了任务的执行;而网络操作系统通常无任务分配功能,网络中每个用户的一个或多个任务通常都在本地计算机上处理。

透明性。分布式操作系统通常能很好地隐藏系统内部的实现细节。包括对象的物理位置、并发控制和系统故障等对用户都是透明的。例如,当用户要访问某个文件时,只需提供文件名而无须知道(所要访问的对象)它是驻留在那个站点上,即可对它进行访问,以即具有物理位置的透明性。网络操作系统的透明性则主要指操作实现上的透明性。例如,当用户要访问服务器上的文件时,只需发出相应的文件存取命令,而无需了解对该文件的存取是如何实现的。

共享性。分布式操作系统支持系统中所有用户对分布在各个站点上的软硬件资源的共享和透明方式访问。而网络操作系统所提供的资源共享功能仅局限于主机或网络服务器中资源,对于其它机器上的资源通常仅有使用该机的用户独占。

健壮性。分布式操作系统由于处理和控制功能的分布性而具有较好的可用性和可靠性,即健壮性。而网络操作系统由于控制功能的集中式特点而使系统重构功能较弱,且具有潜在的不可靠性。

  • Windows系统介绍

3.1 Windows概述

微软自1985年推出Windows 1.0以来,Windows系统经历了十多年变革。从最初运行在DOS下的Windows 3.0,到现在风靡全球的Windows XP、Windows 7、Windows8和Windows10。Windows代替了DOS曾经担当的位子。

3.2 Windows的发展历程

Windows是由微软在1983年11月宣布,并在两年后(1985年11月)发行的。

Windows版本2.0是在1987.11正式在市场上推出的。该版本对使用者界面做了一些改进。2.0版本还增强了键盘和鼠标界面,特别是加入了功能表和对话框。

Windows3.0是在1990年5月22日发布的,它将Win/286和Win/386结合到同一种产品中。Windows是第一个在家用和办公室市场上取得立足点的版本。

3.1版本是1992.4发布的,跟OS/2一样,Windows3.1只能在保护模式下运行,并且要求至少配置了1MB内存的286或386处理器的PC。

在1993年7月发布的Windows NT是第一个支持intel386、486和Pentium CPU的32位保护模式的版本。同时,NT还可以移植到非intel平台上,并在几种使用RISC晶片的工作站上工作。

Windows95是在1995.8月发布的。虽然缺少了NT中某些功能,诸如高安全性和对RISC机器的可携性等,但是95具有需要较少硬件资源的优点。

Windows98在1998年6月发布,具有许多加强功能,包括执行效能的提高、更好的硬件支持以及一国际网络和全球资讯网(WWW)更紧密的结合。

WindowsME是介于98SE和2000的一个操作系统,其出生目的是为了让那些无法符合2000硬件标准同样享受到类似的功能,但事实上这个版本的Windows问题非常多,既失去了2000的稳定性,又无法达到98的低配置要求,因此很快被大众遗弃。

Windows2000的诞生是一件非常了不起的事情,2000年2月17日发布的2000被誉为迄今最稳定的操作系统,其由NT发展而来,同时从2000开始,正式抛弃了9X的内核。时至今日,依然有很多电脑是用这一操作系统。

在2000的基础上,增强了安全特性,同时加大了验证盗版的技术,2001.10.25,“激活”一词成为电脑中最重要的词汇。并且,XP的命名方式也广为散播,各种不同类型的软件“XP”颁布开始出现。某种角度看,Windows XP是最为易用的操作系统之一。

2006年11月,具有跨时代意义的Vista系统发布,它引发了一场硬件革命,是PC正式进入双核、大(内存、硬盘)世代。不过因为Vista的使用习惯与XP有一定差异,软硬件的兼容问题导致它的普及率差强人意,但它华丽的界面和炫目的特效还是值得赞赏的。

Windows 7于2009年10月22日在美国发布,于2009年10月23日下午在中国正式发布。Windows 7 的设计主要围绕五个重点——针对笔记本电脑的特有设计;基于应用服务的设计;用户的个性化;视听娱乐的优化;用户易用性的新引擎。

2012年10月26日,Windows8在美国正式推出。Windows 8支持来自Intel、AMD和ARM的芯片架构,被应用于个人电脑和平板电脑上,尤其是移动触控电子设备,如触屏手机、平板电脑等。该系统具有良好的续航能力,且启动速度更快、占用内存更少,并兼容Windows 7所支持的软件和硬件。另外在界面设计上,采用平面化设计。

Windows 10是微软截至目前发布的最后一个Windows版本,Windows 10大幅减少了开发阶段。自2014年10月1日开始公测,Windows 10经历了Technical Preview(技术预览版)以及Insider Preview(内测者预览版),下一代Windows将作为Update形式出现。Windows10将发布7个发行版本,分别面向不同用户和设备。2015年7月29日12点起,Windows 10推送全面开启,Windows7、Windows8.1用户可以升级到Windows 10,用户也可以通过系统升级等方式升级到Win10。Windows 10大幅减少了开发阶段。自2014年10月1日开始公测,Windows 10经历了Technical Preview(技术预览版)以及Insider Preview(内测者预览版)。

 

  • MacOS系统介绍

4.1 MacOS概述

Mac OS是一套运行于苹果Macintosh系列电脑上的操作系统。Mac OS是首个在商用领域成功的图形用户界面操作系统。现行的最新的系统版本是macOS 10.14 ,且网上也有在PC上运行的Mac系统,简称 Mac PC。

Mac系统是基于Unix内核的图形化操作系统;一般情况下在普通PC上无法安装的操作系统。由苹果公司自行开发。苹果机的操作系统已经到了OS 10,代号为MAC OS X(X为10的罗马数字写法),这是MAC电脑诞生15年来最大的变化。新系统非常可靠;它的许多特点和服务都体现了苹果公司的理念。

另外,疯狂肆虐的电脑病毒几乎都是针对Windows的,由于MAC的架构与Windows不同,所以很少受到病毒的袭击。MAC OSX操作系统界面非常独特,突出了形象的图标和人机对话。苹果公司不仅自己开发系统,也涉及到硬件的开发。

4.2 MacOS四大优点

4.2.1 全屏模式

全屏模式是新版操作系统中最为重要的功能。一切应用程序均可以在全屏模式下运行。这并不意味着窗口模式将消失,而是表明在未来有可能实现完全的网格计算。iLife 11的用户界面也表明了这一点。这种用户界面将极大简化电脑的使用,减少多个窗口带来的困扰。它将使用户获得与iPhone、iPod touch和iPad用户相同的体验。计算体验并不会因此被削弱;相反,苹果正帮助用户更为有效地处理任务。

事实上,Final Cut Pro等一些高端专业软件已经实现了这一点。它们在执行某一任务时,会占据整个屏幕,没有任何浮动窗口。毫无疑问,窗口最终将被完全取代,即使是Photoshop之类的应用而言亦是如此。但网格计算也会产生一些问题。你需要使用户能在不同的任务间高效、毫不混淆地进行切换。从今天的演示来看,苹果或许已经找到了一个巧妙的方法:与触摸手势结合的任务控制。全屏模式的优点在于,简化了计算体验,以用户感兴趣的当前任务为中心,减少了多个窗口带来的困扰,并为全触摸计算铺平了道路。

4.2.2 任务控制

任务控制整合了Dock和控制面板,并可以窗口和全屏模式查看各种应用。

4.2.3 快速启动面板

快速启动面板的工作方式与iPad完全相同。它以类似于iPad的用户界面显示电脑中安装的一切应用,并通过App Store进行管理。用户可滑动鼠标,在多个应用图标界面间切换。与网格计算一样,它的计算体验以任务本身为中心。但它也带来了一个问题,即:Mac电脑的资源管理器Finder是否会从Mac OS X中消失?所有文件均将由文件对话框管理吗?

当前,取消Finder并不现实。它很有可能将继续存在一段时间。但它最终会消失,文件管理将由数据库负责,所有应用可在数据库中分享图片、音乐、文本、PDF文件及其他内容。事实上,如果Spotlight速度更快,表现更好,文件夹完全可以被取消。用户没有时间去管理数以千计的各种文件。快速启动面板简化了操作,用户可以很容易地找到各种应用。但是,某些高端用户可能更喜欢用文件夹树状目录管理应用程序。

4.2.4 应用商店

Mac App Store的工作方式与iOS系统的App Store完全相同。他们具有相同的导航栏和管理方式。这意味着,无需对应用进行管理。当用户从该商店购买一个应用后,Mac电脑会自动将它安装到快速启动面板中。对高端用户而言,这可能显得很愚蠢;但对于普通用户而言,即使利用Mac电脑的拖放系统,安装应用程序仍有可能是一件很困难的事情。

  • Unix/Linux介绍

Linux和Unix都是当今鼎鼎大名的操作系统,可以说改变了这个世界,也是当今科技产业的重要基础。让我们回顾一下他们的发展史吧。

5.1 Unix起源

上世纪六十年代时,大部份计算机都是采用批处理的方式,也就是说,当作业积累一定数量的时候,计算机才会进行处理。贝尔实验室的Ken Thompson,Dennis Ritchie等人开发了Unix。第一版是用汇编语言写的。但是汇编语言做不同机器之间的 移植太过头疼,Dennis Ritchie就发明了C语言,并用C重写了Unix第三版的内核。

5.2 Linux起源

1990年年仅21岁的芬兰赫尔辛基大学学生Linus Torvalds开发了一个类Unix操作系统Linux。严格来讲,Linux这个词本身只表示Linux内核,但在实际上人们已经习惯了用Linux来形容整个基于Linux内核,并且使用GNU 工程各种工具和应用程序的操作系统(也被称为GNU/Linux)。

5.3 Unix历史

1965年,贝尔实验室(BellLads)加入一项由通用电气和麻省理工学院合作的计划,该计划要建立一套多使用者、多任务、多层次的MULTICS操作系统。后来因为项目太为复杂失败。

1969年,其主要开发者Thompson(后被称为Unix之父)和Ritchie领导一组开发者,开发了一个新的多任务操作系统————UNICS,后来被改名为Unix,最初的Unix是用B语言和汇编语言混合编写而成。

1971年,两人在贝尔实验室共同发明了C语言,并于1973用C语言重写了Unix。

1974年,Unix第一次出现在贝尔实验室以外。此后UNIX被政府机关、研究机构、企业和大学注意到,并逐渐流行开来。

1980年,有两个最主要的Unix版本线,一个是Berkeley的BSD UNIX,另一个是AT&T的Unix,两者的竞争最终引发了Unix的战争,最终导致了Unix出现各种各样的变种。

1982年,AT&T基于版本7开发了UNIXSystem III的第一个商业版本,并不再开源。

1992到2001年期间,由于版权问题,AT&T公司于BSD开发组开始了一场将近10年的版权官司。UNIX由于其昂贵的费用,仅局限于大型机的应用:BSD因为版权问题,失去了宝贵的发展时期。

5.4 Linux和Unix的联系

UNIX系统是工作站上最常用的操作系统,它是一个多用户、多任务的实时操作系统,允许多人同时访问计算机,并同时运行多个任务。UNIX系统具有稳定、高效、安全、方便、功能强大等诸多优点,自20世纪70年代开始便运行在许多大型和小型机算机上。

UNIX虽然是一个安全、稳定且功能强大的操作系统,但它也一直是一种大型的而且对运行平台要求很高的操作系统,只能在工作站或小型机上才能发挥全部功能,并且价格昂贵,对普通用户来说是可望不可即的,这为后开的Linux的崛起提供了机会,Linux是一个类UNIX操作系统。

Linux是免费的、不受版权制约、与UNIX兼容的操作系统。

Linux在X86架构上实现了UNIX系统的全部特性,具有多用户、多任务的能力,同时保持了高效性和稳定性,Linux具有如下特点:

  1. 开放性
  2. 完全免费
  3. 多用户
  4. 多任务
  5. 良好的用户界面
  6. 设备独立性
  7. 提供了丰富的网络功能
  8. 可靠的系统安全性
  9. 良好的可移植性

5.5 Unix/Linux开发应用领域介绍

5.5.1 UNIX/Linux服务器

这是目前Unix/Linux应用最多的一个领域,可以提供Web、FTP、Gopher、SMTP/POP3、Proxy/Cache、DNS等服务器,支持服务器集群,支持虚拟主机、虚拟服务、VPN等。

5.5.2 嵌入式Linux系统

嵌入式Linux是将流行的Linux操作系统进行剪裁修改,能够在嵌入式计算机系统上运行的一种操作系统。Linux嵌入式系统能够支持多种CPU和硬件平台,性能稳定,剪裁性好、开发和使用容易。其中包含Embedix、uCLinux、muLinux等。

5.5.3 桌面应用

近年来,Linux系统特别强调在桌面应用方面的改进,并且已达到相当的水平,完全可以作为一种集办公应用、多媒体应用、网络应用等多个方面功能于一体的图形界面操作系统,在办公应用方面,Unix/Linux集成了penOffice、SUN公司的StartOffice以及KOffice等工具。

5.5.4 电子政务

随着Linux的快速发展,Linux已逐渐成为Windows系统重要的竞争力量。尤其是Linux在安全性方面的独特优势,又使得Linux在政府应用领域得到很大的发展。目前一些国家正将其电子政务系统向Linux平台迁移。中国政府也对Linux给予极大的支持。

  • 第六章 服务器操作系统的选择

6.1 服务器操作系统介绍

服务器操作系统一般指的是安装在大型计算机上的操作系统,比如Web服务器、应用服务器和数据库服务器等,是企业IT系统的基础架构平台,也是按应用领域划分的3类操作系统之一(另外2种分别是桌面操作系统和嵌入式操作系统)。同时,服务器操作系统也可以安装在个人电脑上。相比个人版操作系统,在一个具体的网络中,服务器操作系统要承担额外的管理、配置、稳定、安全等功能,处于每个网络中的心脏部位。

服务器操作系统可以实现对计算机硬件与软件的直接控制和管理协调。任何计算机的运行离不开操作系统,服务器也一样。服务器操作系统主要分为四大流派:Windows Server、Netware、Unix、Linux。

6.2 Windows Server

重要版本Windows NT Server 4.0、Windows 2000 Server、Windows Server 2003、Windows Server 2003 R2、Windows Server 2008 、Windows Server 2008 R2 、Windows Server 2012。Windows服务器操作系统派应用,结合.NET开发环境,为微软企业用户提供了良好的应用框架。

优点:Windows Server系统相对于其他服务器系统而言,极其易用,极大降低使用者的学习成本。

缺点:Windows Server系统对服务器硬件要求较高、稳定性不是很好。

应用:Windows Server系统适用于中、低档服务器中。

6.3 Netware

在一些特定行业和事业单位中,NetWare优秀的批处理功能和安全、稳定的系统性能也有很大的生存空间。NetWare常用的版本有Novell的3.11、3.12、4.10、5.0等中英文版。

优点:Netware系统具有优秀的批量处理功能和安全、稳定的系统性能,且兼容DOS命令,支持丰富的应用软件,对无盘站和游戏有着较好的支持,对网络硬件要求较低。

缺点:Netware系统操作大部分依靠手工命令实现,不够人性化;对硬盘识别最高只能达到1G,无法满足TB级数据的存储

应用:Netware系统适用于低档服务器,常运用在中小型企业、学校、游戏厅。

6.4 Unix

Unix服务器操作系统由AT&T公司和SCO公司共同推出,主要支持大型的文件系统服务、数据服务等应用。市面上流传的主要有SCO SVR、BSD Unix、SUN Solaris、IBM-AIX、HP-U、FreeBSDX 。

优点:Unix系统支持大型文件系统服务、数据服务应用,功能强大、稳定性和安全性能好。

缺点:Unix系统操作主要以命令的方式进行,不容易掌握。

应用:大型网站或是大型企、事业局域网中。

6.5 Linux

Linux操作系统虽然与UNIX操作系统类似,但是它不是UNIX操作系统的变种。Torvald从开始编写内核代码时就仿效UNIX,几乎所有UNIX的工具与外壳都可以运行在LINUX上。

优点:Linux系统是开源系统,受到所有开发者的共同监督,已经是非常成熟的服务器系统,并且拥有着一套完整的权限机制,安全性与稳定性都很高。

缺点:Linux系统操作需要一定时间的学习。

应用:Linux系统适用于中、高档服务器中。

 

 

参考书目

  1. 汤子瀛,哲凤屏,汤小丹.计算机操作系统(修订版).西安,西安电子科技大学出版社,2001
  2. 张尤腊,仲萃豪等,计算机操作系统,北京,科学出版社,1979
  3. 孙钟秀,费翔林,骆斌,谢立,操作系统教程(第三版),北京,高等教育出版社,2003
  4. 何炎祥,李飞等,计算机操作系统,北京,清华大学出版社,2006
  5. 陈向群,向勇等,Windows 操作系统原理(第2版),北京,机械工业出版社,2004
  6. 左万历,周长林,计算机操作系统教程(第二版),北京,高等教育出版社,2005
  7. 陈莉君,Linux操作系统内核分析,北京,人民邮电出版社,2000
  8. 徐甲同,网络操作系统,吉林,吉林大学出版社,2000

 

五子棋是一种两人对弈或者人机对弈的纯策略型棋类游戏,应用C语言编写程序可以在计算机上实现两人对弈和人机对弈五子棋功能。人机对弈五子棋程序由开始界面,棋盘,判断胜负和AI等子函数构成;程序中应用了数组、全局变量、图形编程等元素和语句。程序通过棋盘和棋子图像生成、玩家移子与电脑判断分数高低而落子和判断胜负等功能的实现,在Windows操作系统上用CodeBlocks实现了两人对弈和人机对弈模式。

源代码已传github:MapleStory GoBang

第一章    序 言

1.1 设计背景

五子棋相传起源于四千多年前的尧帝时期,比围棋的历史还要悠久,可能早在“尧造围棋”之前,民间就已有五子棋游戏。有关早期五子棋的文史资料与围棋有相似之处,因为古代五子棋的棋具与围棋是完全相同的。在上古的神话传说中有“女娲造人,伏羲做棋”一说,《增山海经》中记载:“休舆之山有石焉,名曰帝台之棋,五色而文状鹑卵。”李善注引三国魏邯郸淳《艺经》中曰:“棋局,纵横各十七道,合二百八十九道,白黑棋子,各一百五十枚”。这段虽没明讲是何种棋类,但至少知道远古就以漂亮的石头为棋子。因而规则简单的五子棋也可能出自当时,并是用石子作棋子。亦有传说,五子棋最初流行于少数民族地区,以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。在古代,五子棋棋具虽然与围棋相类同,但是下法却是完全不同的。正如《辞海》中所言,五子棋是“棋类游戏,棋具与围棋相同,两人对局,轮流下子,先将五子连成一行者为胜”。

传统五子棋的棋具与围棋相同,棋子分为黑白两色,棋盘为15×15,棋子放置于棋盘线交叉点上。 因为传统五子棋只能实现人人对战,而用计算机编程能够实现人机对战,一个人的时候也能体验五子棋的乐趣。因此我们设计了一款拥有双人对战和人机对战的五子棋游戏。

1.2 设计目的

五子棋游戏不仅能增强人们的抽象思维能力、逻辑推理能力、空间想象力,提高人们的记忆力、心算能力等,而且深含哲理,有助于修身养性。五子棋既有现代休闲方式所特有的特征“短、平、快”,又有中国古典哲学所包含的高深学问“阴阳易理”。它既有简单易学的特点,为人民群众所喜闻乐见,又有深奥的技巧;既能组织举办群众性的比赛、活动,又能组织举办高水平的国际性比赛;它的棋文化源渊流长,具有东方的神秘和西方的直观,它是中西方文化的交融点,也是中西方文化交流的一个平台。

自从计算机作为游戏对战平台以来,各种棋类游戏如雨后春笋般纷纷冒出。五子棋是一种受大众广泛喜爱的游戏,其规则简单,变化多端,非常富有趣味性和消遣性。同时具有简单易学、既动手又动脑的特点。同时也为锻炼自己的编程能力。

第二章 需求分析

根据功能需求,将程序分为图形显示、玩家电脑走棋,胜负判断和AI判断落子位置四个函数,以下分析各模块的需求。

2.1 图形库

图形库我们使用的是ACLLib,ACLLib是一个纯教学用途的纯C语言图形库,它并非任何产业界在使用的图形库,也不会有机会发展成为流行的图形库。它只是我们为了C语言学习的目的用的非常简单的图形库。它基于MS Windows的Win32API,所以在所有的Windows版本上都能使用。但是也因此它无法做成跨平台的库在其他操作系统上使用。程序开始运行时,给出五子棋游戏名称界面,让玩家选择双人模式或者人机模式,并选择哪一方先落子。游戏开始后要求生成15×15的棋盘图像,游戏进行过程中,要求实时显示棋盘上已落下的棋子,分出胜负后,在棋盘上方显示哪一方获胜的信息。

2.2 玩家控制模块

程序开始时,需要选择游戏模式,是否让电脑先落子,才能开始游戏;游戏过程中,玩家通过鼠标点击棋盘选择落子;游戏结束时,会显示哪一方获得了胜利。

2.3 胜负判断模块

每当棋盘上多下了一颗棋子,就检测棋盘上新下的这颗棋子,一旦出现五子连线,终止游戏程序,在棋盘上方显示玩家输赢语句。

2.4电脑计分判断落子位置模块

在能下棋的空位置中,假设电脑和玩家下在此处,分别算出各个空位置的分数,并找出最大值。如果最大值是玩家下的,那么电脑就“抢”他的位置,即做到了“防守”。如果最大值是电脑下的,那就让电脑在此处下,即做到了“进攻”,如果存在多个最大值,那么简单的调用随机函数选择其中一个。

第三章 程序详细设计

3.1 开发环境

开发环境:

操作系统:Windows 10 64位

IDE:CodeBlocks 64位

编译器:GNU GCC Compiler

图形库:ACLLib

3.2 ACLLib图形库介绍及开发环境配置

详情请看ACLLib图形库初试

3.3 AI设计思路

五子棋的棋盘是15*15的大小。我的AI算法要求每一次落子之后都要去计算每一个空暇的位置的“分值”,简单的说,我们需要一个存放棋子的数组,表示是否存放了棋子,还要一个计算每一个空格的数组来记录“分数”,这个分数是后期AI用来运算的基础,也是你AI难度控制的点。

我现有的思路就是分两部分。首先是如果是玩家先落子,那么要求电脑AI随即在你落子的地方的任意一个方向,随机落子,这是第一步。接下来以后就正式进入到算法中去。

首先初始化你的分数数组,让他们全部为零。然后在每一次落子之后进行全盘的遍历,如果发现该处为空白,于是检查其四周八个方向,当然如果是边缘位置就相对修改,判断是否出了边界。若在空白处,且发现在某一对角线方向发现有一个其他颜色的棋子,那么相对的给这个空白区域的分数数组加上一定的分值,然后继续往这个方向检测是否还有连续的同一颜色的棋子,若没有则检查其他方向或者检测下一个空白位置。若是还在同一方向上面找到了相同颜色的棋子,那么第二个棋子的出现,你可以给改空白处加上双倍的分值,表明这个空白位置更加重要。依次类推,继续检测。最终AI棋子落在什么地方,依靠的是最后遍历整个分数数组,然后根据分数的高低来进行判断落子落在哪里的。

经过上一遍的遍历,每一次落子都会使得分数数组得到一些变化,每一次都会导致AI判断的变化。在这个基础上,每一次落子还要进行一次对自己本身棋子颜色的一个遍历,判断自己的情况,同时加分加在分数数组之中,这样一来,电脑就会根据自己的棋子的情况以及玩家的落子情况进行判断,哪一个地方更加适合落子。

3.4 函数说明

int isWin(int row, int col,int whoFirst);

判断当棋子下在棋盘上的(row,col)时是否分出胜负。

int Setup();

加载游戏首页的一些图片资源。

void chooseMode(void);

选择游戏的模式,有人机模式和双人模式两种。

void showIndex(void);

显示游戏首页,选择棋子种类。

void initImage1(void);

加载游戏中的一些游戏资源。

void playMusic(void);

加载游戏的背景音乐。

void mouseListener0(int x , int y ,int button ,int event);

监听鼠标,在首页时当鼠标移至指定位置时该位置的文字显示高亮,以及鼠标的点击位置。

void mouseListener1(int x , int y ,int button ,int event);

监听鼠标,在选择游戏模式界面时当鼠标移至指定位置时该位置的文字显示高亮,以及鼠标的点击位置。

void mouseListener2(int x , int y ,int button ,int event);

监听鼠标,判断人机模式下玩家的落子坐标。

void mouseListener3(int x , int y ,int button ,int event);

监听鼠标,判断双人模式下玩家的落子坐标。

char* myStrCat(char *dst,const char *src);

自己写的一个字符串处理函数,处理资源路径用。

void gameMode0(void);

人机模式。

void gameMode1(void);

双人模式。

void timerListener(int id);

定时器,用于给上一个落子地点产生闪烁提示玩家。

char * myStr(char *str,int n,int m);

自己写的一个字符串处理函数,处理资源路径用。

void Robot(int *x, int *y, int *Sum);

人机模式判断落子。

void Findscore(int *x, int *y);

查找评分最高的坐标。

void ChessOne(int *x, int *y);

玩家走第1步时的落子。

void ChessScore();

给当前棋盘没有棋子的地方打分。

 

第四章 游戏运行展示

描述

有一行由 N 个数字组成的数字字符串,字符串所表示的数是一正整数。移除字符串中的 K 个数字,使剩下的数字是所有可能中最小的。

假设:

  • 字符串的长度一定大于等于 K
  • 字符串不会以 0 开头

输入

一行由 N 个数字组成的数字字符串(0 < N < 20),和一个正整数 K(K < N),两个数据由空格隔开,如:1432219 3。

输出

移除 K 位后可能的最小的数字字符串。 如 1432219 移除 4, 3, 2 这 3 个数字后得到 1219,为所有可能中的最小值。

输入样例

1432219 3
10200 1

输出样例

1219
200

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;


string removeKdigits(string num, int k)
{
    bool flag = false;//判断是否有前缀0
    string res = "";
    string result = "";
    int temp = 0;
    stack<int>a;
    for(int i = 0; i < num.size(); i++)
    {
        int number = num[i] - '0';
        while( !a.empty() && a.top() > number && k>0)
        {
            a.pop();
            k--;
        }

        a.push(number);
    }
    while(!a.empty() && k>0)
    {
        a.pop();
        k--;
    }
    while(!a.empty())
    {
        temp = a.top();
        stringstream s1;
        string s2;
        s1<<temp;
        s1>>s2;
        res = res+s2 ;
        a.pop();
    }
    for(int i = res.length()-1; i>=0; i--)
    {
        if(res[i]!='0')
        {
            flag = true;
        }
        if(flag)
        {
            result = result + res[i];
        }
    }
    if(result.size() == 0){
        result = "0";
    }
    return result;
}

int main()
{
    string s;
    vector<int>a;
    int k = 0;
    int cnt = 0;
    while(cin>>s>>k)
    {
        cout<< removeKdigits(s,k)<<endl;
    }
}