Posts Tagged ‘dotNet’

  • 配置ASP.NET中使用SQL Server模式的Session State

    Date: 2009.09.18 | Category: Web Back-end | Response: 0

    作者通过亲自试验,完成了在Plesk平台下的SQLServer模式会话状态的配置。具体步骤如下:

    1. 为回话状态建立或是选择相应的数据库Database(Create New Database)
    2. 执行会话状态模板SQL语句
      首先进入文件夹C:\Windows\Microsoft.NET\Framework\version_ID\,对于ASP.NET 2.0来说,一般version_ID是v2.0.50727。然后找到InstallSqlStateTemplate.sql,并将文中所有Data­ba­se­Na­me­Pla­ce­Ho­lder替换为你自己的数据库名称,最后将此SQL拖到数据库上执行
    3. 此时也许你会发现,测试SQL语句没问题,但是执行的时候出现了一些问题如下:
      ————————————————-
      Sta­r­ting exe­cu­tion of InstallSqlStateTemplate.SQL
      ————————————————-

      ————————————————–
      Note:                                            
      This file is inclu­ded for backward compa­ti­bi­lity 
      only.  You should use aspnet_regsql.exe to install
      and unin­stall SQL session state.                 

      Run ‘aspnet_regsql.exe -?’ for details.        
      ————————————————–
      If the job does not exist, an error from msdb.dbo.sp_delete_job is expe­cted.
      Msg 229, Level 14, State 5, Pro­ce­dure sp_delete_job, Line 1
      The EXECUTE per­mi­ssion was denied on the object ‘sp_delete_job’, data­base ‘msdb’, schema ‘dbo’.
      If the cate­gory already exi­sts, an error from msdb.dbo.sp_add_category is expe­cted.
      Msg 229, Level 14, State 5, Pro­ce­dure sp_add_category, Line 1
      The EXECUTE per­mi­ssion was denied on the object ‘sp_add_category’, data­base ‘msdb’, schema ‘dbo’.
      Msg 229, Level 14, State 5, Pro­ce­dure sp_add_job, Line 1
      The EXECUTE per­mi­ssion was denied on the object ‘sp_add_job’, data­base ‘msdb’, schema ‘dbo’.

      ————————————————–
      Comple­ted exe­cu­tion of InstallSqlStateTemplate.SQL
      ————————————————–
    4. 不必担心,这个主要是由于用户权限不够而不能将某些规划任务加入到数据库计划中。我们无法将过期的一些session数据删除,不过可以手动操作,或是请求你的主机运营商帮忙

    5. 更新web.config文件:
      <session­State mode=“SQLServer” allowCustomSqlDatabase=“true” sqlConnectionString=“data source=localhost;initial catalog=数据库名;user id=用用户名;password=密码” cookieless=“false” timeout=“20” />

     

    Refe­rence:

    • Share/Bookmark
  • 8020 Distributed Dental Management System” Milestone 1 Code Complete

    Date: 2009.08.29 | Category: Programming Language | Response: 1

    8020 Dist­ri­bu­ted Den­tal Mana­ge­ment System” is a pro­ject and a pro­g­ram based on .NET Fra­me­work 3.5 and WCF (Win­dows Commu­ni­ca­tion Foun­da­tion) Tech­ni­que. It is also a pro­ject for my postg­ra­dua­tion the­sis. It is desi­g­ned for seve­ral con­ca­te­na­ted den­tal cli­nics, in ano­ther word, a den­tal cli­nics group, to build their own netwo­r­king and syn­ch­ro­ni­za­ble mana­ge­ment system. It will combine and keep syn­ch­ro­ni­zing on patients’ medi­cal reco­rds and their teeth X-ray pho­tos between clinics.

    With a whole month’s effort, I just fini­shed desi­g­ning, coding on Mile­stone 1 of 8020System. I lea­rnt WCF Tech­ni­que, deci­ded to code this pro­ject on .NET, desi­g­ned both of data­base and pro­g­ram archi­te­cture, and then pain­ted win­dows forms with plenty of events and fun­ctions bound on, pro­g­ra­mmed data access tier and busi­ness logic tier. All the work on the pro­ject is done by myself. Maybe it is a small task for a pro­g­ra­mming team, but actua­lly it is a huge pro­ject for me.

    image
    Patient Info­ma­tion Page

    For the the­sis inspe­ction on this Sun­day, I have to make a mile­stone for my pro­ject to let my tutor check it out and give me some sug­ge­stion. I just imple­me­ted some basic fun­ctions such as patient info­r­ma­tion, den­tal users inclu­ding den­ti­sts and nur­ses man­ga­ment, work sche­du­ling, reserva­tion on so on. There is a spe­cial fun­ction in the pro­g­ram, and we can send/receive short messa­ges using my pro­ject. I enri­ched its fun­ctions and give much conve­nience to nur­ses. With a SMS modem and a SIM card, you can send/receive any messa­ges you want to the patients and workers.

    image
    SMS Page

    In the server tier, I put a visi­ble con­t­rol pro­g­ram and use Web Servi­ces with WS-Security for safely data tran­sfer­ring. And I also imple­men­ted duplex tran­smi­ssion between server and clients although HTTP pro­to­col is an sta­te­less one. Thanks for the power­ful WCF! It’s cool!

    imageServer Side

    And I used abun­dant LINQ sen­ten­ces for high effi­cient pro­g­ra­mming and less code lines. Thanks for the intern expe­rience on Mic­ro­soft MBD, I can use LINQ habitually.

    For the mee­ting of Sun­day and first the­sis draft due on middle Septe­mber, I have to tur­ned myself to docu­men­ta­tion making. I should write down the first cha­pter of my the­sis and a dire­ctory of con­tents tomo­r­row (actua­lly it is today!). Keep walking and keep imp­roving myself.

    • Share/Bookmark
  • SMSVote @ BJTU 2008-11-30

    Date: 2008.12.01 | Category: BJTU, Programming Language, Software | Response: 0

    昨天回到了母校交大,参与了一次交大校级的“百科知识竞赛”。由于这次竞赛上使用了本科时候和邱振生、王正韬一起开发的短信投票平台,所以倍感亲切。

    交大没什么变化,虽然已经过去一年多了,这座有着百年历史的老校依然在这里默默地哺育着一代又一代的年轻人。唯一不同的是,在我看来,校园内稚嫩的面孔多了很多。自己当时也是那样子吧,每天生活无忧无虑的,不会太考虑自己今后所要承受的磨砺,而是享受校园悠然而快节奏的生活。

    回到主题,谈谈自己的短信投票平台吧。去年在北大软院举办的十佳歌手大赛时候也使用了这样的平台,但不同的是,在北软当时只是使用了一块幻灯幕布,展示区域较小,没有体现出应有的效果;而在交大的天佑会堂里面,直接将投票幻灯投向大墙壁,效果很不错。

    DSC00352 DSC00354

    关于程序,是我们仨(软三工作室)在大三时候开发的。这其中还有一个小插曲:

    最开始写的这个程序做了很多复杂的功能,比如一条短信可以分别给几个人投几票,一个手机号可以给几个选手投票,而这些投票的数量是可以接受控制的;另外系统也可以通过同一手机号同时接收短信短信投票与现场评论,最后还可以提供抽奖环节。这样一个系统,在开始的时候,我们做的并不好。每个30秒钟进行一次定时结果统计;同时如果收到短信以后也会自动刷新统计结果。这样,统计这个函数被大量调用。但一个可怕的问题是,我们的统计函数的时间复杂度是O(n3)……最开始票数少的时候还好,有一次组织方定了一个非常宽松的要求,每个人可以投十票。虽然只是一个院级的活动,但是收到了将近10000票。10000的三次方……每隔半秒钟不到(接收一条短信的时间间隔)就要刷新这么一下次,系统当时就崩溃了。

    后来我们改进了算法,利用空间换取时间,把已经收到的进入了数据库的统计都存在内存中,每次投票统计只是刷新新进入的投票。这样,问题就迎刃而解,时间复杂度也降到了O(1)。压力测试后,接受20万条短信没问题(再大的就没有测试过了)。

    面对自己亲手做成功的产品,心里还是很高兴的,毕竟所学的东西没有白学。设计模式、算法与程序设计、.NET应用程序设计……不得不说,交大的很多本科课程开的非常好。赞一下。

    下一次回交大,不知啥时候了。但心情都不会平静,这是我的母校,这里有我很多最好的朋友。

    • Share/Bookmark
  • 浅谈ASP.net中使用WebServices的安全性保证

    Date: 2008.11.05 | Category: Programming Language, Web Back-end | Response: 0

    在开发一些在线业务的时候,对于一些客户端程序,我们需要将数据存储在网络上,即使用传统的C/S结构。随着WebServices的出现,我们可以用很低的成本在成熟的网络上架构这种结构,不必单独去购买数据中心服务器了。

    实现的方法主要是:购建一个支持asp.net 2.0以上版本的虚拟服务器,然后在上面部署WebServices环境,通过调用asmx的方法对后台的数据库(MySQL、MS-SQL、Access等)进行数据库访问。而在客户端方面,我们就可以使用窗体了而不是Browser。通过调用后台的Services完成数据的交换。

    数据交换容易,搭建WebServices也不是一件难事。但是难点在于,我们如何在这种基于HTTP下(没有SSL和证书)、透明的WebServices下,来保证Services的安全性?现在世面上的虚拟主机空间都不支持https。如何快速开发一个小DataServices呢?当然,我们第一步的考虑肯定是在每一个Service里面加上两个额外的参数:用户名和密码。这个可行,但是复杂度增加不少;后来我也考虑过使用Session来做。但是这种方法,只能适合在浏览器上的测试;而对于实际的客户端程序来讲,无疑没有什么作用。

    通过学习,我掌握了一种在SOAP头中增加身份信息描述的方法;在客户端,只需要保存一个相关的身份验证对象,每次调用Services的时候就可以不必去考虑身份的问题了。Stub端会将身份信息绑定到SOAP Head中。

    每次访问服务器,便会触发一个HttpModule来对身份进行验证。在Services体中,我们只需要判断是否已经通过身份验证即可。

    首先我们要构造这个HttpModule。这是一个继承了IHttpModule接口的类,用来截获来自客户端的XML文件,并对其SOAP Head进行解析,找出我们需要的用户名和密码的信息,并交由WebServiceAuthenticationEventHandler所触发的事件来去判断身份。

    using System;
    using System.Web;
    using System.IO;
    using System.Xml;
    using System.Xml.XPath;
    using System.Text;
    using System.Web.Services.Protocols;
    
    namespace JingZhiWebService
    {
    public sealed class WebServiceAuthenticationModule : IHttpModule
    {
    private WebServiceAuthenticationEventHandler
    _eventHandler = null;
    
    public event WebServiceAuthenticationEventHandler Authenticate
    {
    add { _eventHandler += value; }
    remove { _eventHandler -= value; }
    }
    
    public void Dispose()
    {
    }
    
    public void Init(HttpApplication app)
    {
    app.AuthenticateRequest += new
    EventHandler(this.OnEnter);
    }
    
    private void OnAuthenticate(WebServiceAuthenticationEvent e)
    {
    if (_eventHandler == null)
    return;
    
    _eventHandler(this, e);
    if (e.User != null)
    e.Context.User = e.Principal;
    }
    
    public string ModuleName
    {
    get { return "WebServiceAuthentication"; }
    }
    
    void OnEnter(Object source, EventArgs eventArgs)
    {
    HttpApplication app = (HttpApplication)source;
    HttpContext context = app.Context;
    Stream HttpStream = context.Request.InputStream;
    
    // Save the current position of stream.
    long posStream = HttpStream.Position;
    
    // If the request contains an HTTP_SOAPACTION
    // header, look at this message.
    if (context.Request.ServerVariables["HTTP_SOAPACTION"]
    == null)
    return;
    
    // Load the body of the HTTP message
    // into an XML document.
    XmlDocument dom = new XmlDocument();
    string soapUser;
    string soapPassword;
    
    try
    {
    dom.Load(HttpStream);
    
    // Reset the stream position.
    HttpStream.Position = posStream;
    
    // Bind to the Authentication header.
    soapUser =
    dom.GetElementsByTagName("User").Item(0).InnerText;
    soapPassword =
    dom.GetElementsByTagName("Password").Item(0).InnerText;
    }
    catch (Exception e)
    {
    // Reset the position of stream.
    HttpStream.Position = posStream;
    
    // Throw a SOAP exception.
    XmlQualifiedName name = new
    XmlQualifiedName("Load");
    SoapException soapException = new SoapException(
    "Unable to read SOAP request", name, e);
    throw soapException;
    }
    
    // Raise the custom global.asax event.
    OnAuthenticate(new WebServiceAuthenticationEvent
    (context, soapUser, soapPassword));
    return;
    }
    }
    }

    接着是身份验证的事件。这个事件继承了Even­tA­rgs,并增加了相应的用户名密码字段。

    using System;
    using System.Web;
    using System.Security.Principal;
    
    namespace JingZhiWebService
    {
    public delegate void WebServiceAuthenticationEventHandler(Object sender, WebServiceAuthenticationEvent e);
    
    public class WebServiceAuthenticationEvent : EventArgs
    {
    private System.Security.Principal.IPrincipal _IPrincipalUser;
    private HttpContext _Context;
    private string _User;
    private string _Password;
    
    public WebServiceAuthenticationEvent(HttpContext context)
    {
    _Context = context;
    }
    
    public WebServiceAuthenticationEvent(HttpContext context,
    string user, string password)
    {
    _Context = context;
    _User = user;
    _Password = password;
    }
    public HttpContext Context
    {
    get { return _Context; }
    }
    public IPrincipal Principal
    {
    get { return _IPrincipalUser; }
    set { _IPrincipalUser = value; }
    }
    public void Authenticate()
    {
    GenericIdentity i = new GenericIdentity(User);
    this.Principal = new GenericPrincipal(i, new String[0]);
    }
    public void Authenticate(string[] roles)
    {
    GenericIdentity i = new GenericIdentity(User);
    this.Principal = new GenericPrincipal(i, roles);
    }
    public string User
    {
    get { return _User; }
    set { _User = value; }
    }
    public string Password
    {
    get { return _Password; }
    set { _Password = value; }
    }
    public bool HasCredentials
    {
    get
    {
    if ((_User == null) || (_Password == null))
    return false;
    return true;
    }
    }
    }
    }

    我们可以看到,通过触发这个事件,就可以对用户身份进行确认了,进而触发Authen­ti­cate()方法,来对身份进行登记。

    当然,我们还需要一个属性框架来存放这个身份。这个类当然必须需要可以序列化(Seria­li­za­ble)来实现数据的传递。

    using System;
    using System.Data;
    using System.Configuration;
    using System.Web;
    using System.Web.Security;
    using System.Web.Services.Protocols;
    
    namespace JingZhiWebService
    {
    public class WebServiceAuthentication : SoapHeader
    {
    public string User;
    public string Password;
    
    public WebServiceAuthentication() { }
    
    public WebServiceAuthentication(string user, string password)
    {
    this.User = user;
    this.Password = password;
    }
    }
    }

    为了能够让这个模块正常工作,我们必须要在Web.Config里面声明它。将下述代码放到system.web下:

    <httpMo­du­les>
    <add type=“JingZhiWebService.WebServiceAuthenticationModule” name=“WebServiceAuthentication”/>
    </httpModules>

    最后,在Global.asax中来触发这个身份验证的事件。需要说明的是,事件绑定的时间不应该处于Application_Start时。那个时候Module还没有启动,所以在这个时候,我们无法取得到我们的Module运行时对象,事件的绑定也就无从谈起。经过测试,放在Application_BeginRequest是个不错的选择。

    protected void Application_BeginRequest(object sender, EventArgs e)
    {
    WebServiceAuthenticationModule wam = (WebServiceAuthenticationModule)this.Modules["WebServiceAuthentication"];
    wam.Authenticate += new WebServiceAuthenticationEventHandler(wam_Authenticate);
    }
    
    ///
    /// User Validation Process
    ///
    ///
    
    ///
    
    void wam_Authenticate(object sender, WebServiceAuthenticationEvent e)
    {
    if (e.User == "putyourusernamehere" && e.Password == "putyourpasswordhere")
    {
    e.Authenticate(new string[]{"user"});
    }
    }

    通过上述的身份验证,我们就可以使用带有身份识别的Servi­ces了。

    来看个例子如何使用身份识别。

    using System;
    using System.Collections;
    using System.ComponentModel;
    using System.Data;
    using System.Web;
    using System.Web.Services;
    using System.Web.Services.Protocols;
    
    namespace JingZhiWebService
    {
    [WebService(Namespace = "http://www.techwork.cn/")]
    [WebServiceBinding(ConformsTo = WsiProfiles.BasicProfile1_1)]
    [ToolboxItem(false)]
    public class DataService : System.Web.Services.WebService
    {
    public WebServiceAuthentication authentication;
    private string UserRole = "user";
    
    [WebMethod]
    [SoapHeader("authentication")]
    public bool UserAuthentication()
    {
    if (User.IsInRole(UserRole))
    {
    return true;
    }
    return false;
    }
    }
    }

    那么客户端呢?

    public static bool Authentication(string username, string password)
    {
    JingZhiDataService.WebServiceAuthentication auth = new JingZhi.JingZhiDataService.WebServiceAuthentication();
    auth.User = username;
    auth.Password = password;
    ds.WebServiceAuthenticationValue = auth;
    return ds.UserAuthentication();
    }

    我们可以在类中保存这个ds对象。每次调用WebServices的时候,直接用已经进行过身份认证的,绑定了user和password的DataService对象来调用服务。至此,我们完成了身份验证与Services的绑定。身份的问题不再是一个烫手的山芋那般不好处理了。

    这种方式,对于一般的要求不是太高的个人和小型企业的业务,是个不错的选择。

    最后我们再来看看实际的SOAP包是什么样子的吧。红色的部分,则是我们通过努力实现的身份验证。可以看到,我们已经将他们放入了SOAP Head中。

    Request部分:

    <?xml version=“1.0″ encoding=“utf-8″?>
    <soap12:Envelope xmlns:xsi=“http://www.w3.org/2001/XMLSchema-instance” xmlns:xsd=“http://www.w3.org/2001/XMLSchema” xmlns:soap12=“http://www.w3.org/2003/05/soap-envelope”>
    <soap12:Hea­der>
    <WebServi­ceAu­then­ti­ca­tion xmlns=“http://www.techwork.cn/”>
    <User>string</User>
    <Password>string</Password>
    </WebServiceAuthentication>
    </soap12:Header>
    <soap12:Body>
    <Use­rAu­then­ti­ca­tion xmlns=“http://www.techwork.cn/” />
    </soap12:Body>

    </soap12:Envelope>

    Response部分:

    HTTP/1.1 200 OK
    Content-Type: application/soap+xml; charset=utf-8
    Content-Length: length

    <?xml version=“1.0″ encoding=“utf-8″?>
    <soap12:Envelope xmlns:xsi=“http://www.w3.org/2001/XMLSchema-instance” xmlns:xsd=“http://www.w3.org/2001/XMLSchema” xmlns:soap12=“http://www.w3.org/2003/05/soap-envelope”>
    <soap12:Body>
    <Use­rAu­then­ti­ca­tion­Re­sponse xmlns=“http://www.techwork.cn/”>
    <UserAuthenticationResult>boolean</UserAuthenticationResult>
    </UserAuthenticationResponse>
    </soap12:Body>
    </soap12:Envelope>

    综上,我们至此完成了用户名和密码的传输工作。

    还有一个问题:http协议是明文传输的,那么我怎样保证用户名密码不被截获呢?答案是:不可能。对于我们来讲,还可以做的,是将我们的用户名密码加密。对于用户名,可以使用一种可回溯的明文加密方法;对于密码,建议直接选择MD5或者SHA1吧。System.Security.Cryptography命名空间下有MD5SHA1的加密方法。这个到哪都能照出来,我也搜了一下,可以直接使用了:

    当然,我们也可以使用Web.Config里面的Form认证方式。使用FormsAuthentication.HashPasswordForStoringInConfigFile()函数可以判断。这里就不再赘述了。

    以高效率、低成本部署拥有足够安全性和灵活性的网络应用程序,是一种不错的选择。

    • Share/Bookmark
  • 小程序

    Date: 2008.10.30 | Category: Programming Language, Web Back-end | Response: 1

    用了近三个晚上开发了一个小程序——“精致三面翻”售出存档表,主要帮助我爸的公司进行数据整理。用到了ASP.net 2.0的技术。

    image

    image image

    虽然程序很小,但是相信对于父亲的公司还是挺有帮助的。开发过程中有一些小体会和经验:

    • 程序并不是代码越优美越好。对于一些小程序,快速开发,省略一些无关紧要的问题显得非常重要。对于软件工程科班出身的我,编码时命名很难不想到匈牙利命名法。。如果我们把时间都花在校正变量上,那么无异于浪费。我的策略:将主要用到的TextBox/DateTimePicker等一些类的对象加以合理命名,其它的则随系统的自身命名好了。另外数据库选用了Access,表名、字段名全部中文。。加上.net 2.0的DataSet,开发非常快捷。。时间多半花在了画界面上。。
    • 如果程序中出现几个大块相同的地方,建议把他们做成User­Con­t­rol加以调用。省时省力。
    • 如果你使用的是Access数据库,在进行参数传递的时候,变量名不要是SqlServer中的“select * from table where username=@username”,而应该是:“select * from table where username=?”。问号足矣。这点也花了我一定的时间。
    • 对于.net的数据库,配置文件对它的路径描述是:|DataDirectory|。那么我们怎么找到这个文件夹呢?答案是:Application.LocalUserAppDataPath。这个有的时候很重要。。比如在我的备份功能那块。。
    • 利用.net fra­mwork 2.0发送mail的代码不用找了,我提供一个能用于gmail的,放在下面了。
    • IconWorkshop软件做出来的icon很好看!
    • That’s it. ^_^
    public void SMTP(string from, string to, string bcc, string subject, string body, string attachment)
    {
    MailMessage mailMsg = new MailMessage();
    mailMsg.From = new MailAddress(from);
    mailMsg.To.Add(to);
    mailMsg.Subject = subject;
    mailMsg.IsBodyHtml = true;
    mailMsg.BodyEncoding = Encoding.UTF8;
    mailMsg.Body = body;
    mailMsg.Attachments.Add(new Attachment(attachment));
    mailMsg.Priority = MailPriority.Normal;
    // Smtp configuration
    SmtpClient client = new SmtpClient();
    client.Credentials = new NetworkCredential("xxx@gmail.com", "thepassword");
    client.Port = 587; //or use 465
    client.Host = "smtp.gmail.com";
    client.EnableSsl = true;
    object userState = mailMsg;
    try
    {
    //you can also call client.Send(msg)
    client.SendAsync(mailMsg, userState);
    client.SendCompleted += new SendCompletedEventHandler(client_SendCompleted);
    }
    catch (SmtpException ex)
    {
    //Catch errors...
    MessageBox.Show("Error:" + ex.Message);
    toolStripStatusLabel1.Text = "Error...";
    this.Enabled = true;
    }
    • Share/Bookmark
  • 软件实现技术课

    Date: 2008.08.03 | Category: Microsoft, PKU | Response: 0

    软件实现技术课结课了,最终小组取得了第二名的成绩。

    这门课,是由软微学院和微软联合创办的课程,虽然开始选这门课的时候,更多的是看重的微软的这个名字。不过学完之后看过来,的确学到了一些很有用的东西,受益匪浅。

    总结一下:

    • Lea­r­ning by Doing
      通过实践来学习,掌握技能和技巧。要努力提高自己遇到问题解决问题的能力。
    • 算法设计要提到一个非常高的重视程度
      尽管在开发时,架构、框架、管理……一切都很重要,但是算法绝对不可以忽视,有了足够好的算法,系统才能更加稳定更加健壮,也更加完善地运行
      加强自己的算法设计能力,通过研究算法,加强自己对操作系统的认识,提高逻辑思维能力
    • 做就要做最好的
      在任何时候,能够被大家记住的,只有第一名。在参与竞争时,要给自己暗示:只有两个名次,要么做第一名,要么做除了第一名以外的并列最后一名。
      我们都记得神五飞船杨利伟的名字,可是又有多少人还能马上叫出的神六的两位航天员的名字呢?
    • 向比自己做的好的人和团队借鉴经验
      正所谓踏在巨人的肩膀上前进,这样才能事倍功半
    • 各自在团队中扮演好自己的角色,做出自己应有的贡献
      没有PM的组织,团队是一团散沙;没有Dev的辛勤开发,系统无法运行;没有Test的认真测试,系统正确性无法保证。三足鼎立,就像三角形,缺一角,就变得不够稳定了。
    • Nothing is impo­ssi­ble
      没有什么是做不到的,只要你想,并且为之付出足够的努力

    我组的PM:杰哥,获得了整个课程的最佳PM奖,恭喜杰哥!没有他,小组的沟通与进度便无法保证,我也没有办法能把自己足够的精力集中到开发中。

    最后,其实发现,我还是对开发更感兴趣一些,呵呵。

    • Share/Bookmark
  • 最大子序列算法

    Date: 2008.07.03 | Category: Algorithm, Microsoft | Response: 0

    周日的软件技术实现课上,Xin Zou 老师给我们出了一道题。在一个数字数组里面,求一个连续数字之和的最大值子序列,返回最大的值,以及这个子序列的起始位置、终止位置。

    我们小组使用了动态规划算法实现,实现方法如下(用C++实现,关键代码):

    /*
    问题描述:
    有一串数字(可正可负的int,放在数组Num里),要求找到起始位置start和终止位置end,使得从start位置到end位置的所有数字之和最大,返回这个最大值max。

    算法阐述:
    最简单的方法是用动态规划算法实现:
    设 f[x] 为以 a[x] 终止且包含 a[x] 的最大序列的和,有:
       f[1] = a[1];
       f[x+1] = f[x] > 0 ? f[x] + a[x+1] : a[x+1]
    那么最大子序列的和就是 f[1] .. f[n] 中最大的一个。
    算法的时间复杂度为O(n)
    */

    void MaxSubSeq::MaxSubseq_DP(int nums[], int count, int &resStart, int &resEnd, int &resMax)
    {
        // 求数组nums[]中连续子序列的最大和,并标出该子序列
        // 设 f[x] 为以 a[x] 终止且包含 a[x] 的最大序列的和,有:
        //    f[1] = a[1];
        //    f[x+1] = f[x] > 0 ? f[x] + a[x+1] : a[x+1]
        // 那么最大子序列的和就是 f[1] .. f[n] 中最大的一个
        int start, max;
        int i;
         start = resStart = resEnd = 0; //初始化当前子序列和最大子序列为nums[0]
        max = resMax = nums[0];

        for (i = 1; i < count; ++i) {
            if (max > 0) {
                max += nums[i];
            } else {
                max = nums[i]; //抛弃当前子序列
                 start = i; //开始新的子序列搜索
            }
            if (resMax < max) { //更新最大子序列
                 resMax = max;
                 resStart = start;
                 resEnd = i;
            }
        }//for

        return;
    }

    Read the rest of this entry »

    • Share/Bookmark

Paul’s Online Services

Dynamic Tag Cloud

Recent Posts

Recent Comments

Tags

2008.11.Trip-of-GuangXi ASP.net C++ China Chrome css dotNet FCGuoAn Firefox Football gmail IBM IE IIS IT Association Joke Microsoft music mysql NLP Nokia ntfs NumPy OpenSolaris open source Open Team php pidgin PKUSS Python Python Challenge qq Samba SciPy Learning shell solaris SQL SUN Thunderbird Travel web host Win 7 WordPress X11 zfs