Static Oneplus 不可控制论

2011/03/09 - by Oneplus • ACM Group程序设计实践哈尔滨公交系统

程序设计实践一 - 第二课


课程提纲

  • 上节课的回归与作业讲解
  • 分治
  • 二分算法
    • 例一:求x=√9.8
      • 题目描述
      • 算法过程演示
      • 算法分析
      • 伪代码与代码
    • 例二:二分查找
      • 题目描述
      • 题目分析
      • 伪代码与代码
      • 复杂度分析
    • 讨论:整数二分的最好写法
      • 例一
      • 例二
    • 例三:求一列有序数中第一个大于等于某数的数
      • 题目描述
      • 题目分析
      • 伪代码与代码
      • 拓展:最大化最小/最小化最大的一般分析方法
    • 教你偷懒:lower_bound、upper_bound
    • 离线算法与在线算法
    • 引例:只有添加操作的在线求一列数的最大值
      • 题目描述
      • 题目分析
    • 例四:支持添加和删除最大操作的在线求一列数的最大值
      • 题目描述
      • 算法一
      • 算法二
      • 总结算法一二的悲剧之处
    • 堆的性质
    • 堆的操作
      • 上浮
      • 下沉
      • 删除最大
      • 添加
    • 伪代码与代码
    • 教你偷懒:priority_queue

简单的讲义

讲义请看这里

PPT请看这里

录了30多分钟的课堂录音

这节课是用自己的笔记本进行的演示,录到了课堂录音。原文件噪音非常多,用Goldwave处理了一下,果然好了不少。

</embed>

自我检讨

  • 因为课程录了音,所以对于自己的授课内容有了一个比较清楚的认知。
  • 从这节课的录音来看,我讲课的一些问题包括:重复冗余严重,二分的算法过程被说了三次、二分复杂度证明说了两次;语气平淡,重点不突出;声音比较小,有点无力。
  • 而且这节课在多媒体的问题上花的时间有点多。大概有十五分钟都是在调多媒体…
  • 自己笔记本的时间和8503机器的时间不同步,在课间休息时间的问题上把握得不好。
  • 现在看,自己的讲义是挺混乱的。课件做得尤其糟糕。
  • 这里需要向上课的同学道歉,第二课我的准备工作的确有不足。这节课的准备中,把太多时间花在demo上,以至于没有足够的时间去思考要讲什么内容。下节课demo的东西比较少,我会认真准备课程内容的。

浮云一样的heap的demo

其实这个flash动画也是我做的…

演示二分时用的Java代码

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.Panel;
import java.io.*;
import java.text.DecimalFormat;

public class bisearch extends JFrame implements ActionListener {
    public bisearch() {
        setLayout(new FlowLayout(FlowLayout.LEFT));
        setSize(500, 400);
        setBackground(Color.white);
        
        nextButton = new Button( "Next" );
        nextButton.addActionListener( this );
        add( nextButton );
        
        init();
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }
    
    public void init() {
        lowerBound = f( leftBound );
        upperBound = f( rightBound );
        low = 3.0;
        high = 4.0;
        //System.out.println( lowerBound + " " + upperBound );
    }
    
     public void paint( Graphics g ) {
         point p1 = new point();
         point p2 = new point();
         p1 = toPoint(2.7, 0.0 );
         p2 = toPoint(4.3, 0.0 );
         x_axis = p1.getY();
         g.drawLine( p1.getX(), p1.getY(), p2.getX(), p2.getY());
        g.drawLine( 40, 0, 40, 400);
        g.drawString( "y axis", 35, 75 );
        g.drawString( "x axis", 450, x_axis );
         
         for( double i = leftBound; i <= rightBound; i = i + eps ) {
             double x = i, xx = i + eps;
             double y = f( x ), yy = f( xx );
             
             p1 = toPoint( x , y );
             g.drawLine( p1.getX(), p1.getY(), p1.getX(), p1.getY());
         }
         p1 = toPoint( 3.0, f(3.0) );
         p2 = toPoint( 4.0, f(4.0) );
         g.drawOval( p1.getX() - 3, p1.getY() - 3, 6, 6);
         g.drawOval( p2.getX() - 3, p2.getY() - 3, 6, 6);
         g.drawLine( p1.getX(), p1.getY(), p1.getX(), x_axis );
         g.drawLine( p2.getX(), p2.getY(), p2.getX(), x_axis );
         new DecimalFormat( "0.00" );
         g.drawString( Double.toString( 3.0 ), p1.getX(), x_axis + 12);
         g.drawString( Double.toString( 4.0 ), p2.getX(), x_axis + 12);
         //System.out.println( p1.getX() + " " + p1.getY() );
    }
     
    public double f( double x ) {
        return x * x - 9.8;
    }
    
    public point toPoint( double x, double y ) {
        double xx = ( x - leftBound ) / ( rightBound - leftBound ) * 500.0;
        double yy = ( y - upperBound ) / ( lowerBound - upperBound ) * 400.0;
        
        point ret = new point( (int)xx , (int)yy );
        return ret;
    }
    
    public void actionPerformed( ActionEvent event ) {
        if( event.getSource() == nextButton ) {
            if( high - low > 0.001 ) {
                mid = ( low + high ) * 0.5;
                new DecimalFormat( "0.00" );
                point p1 = toPoint( mid, f(mid) );
                getGraphics().drawOval( p1.getX() - 3, p1.getY() - 3, 6, 6);
                getGraphics().drawLine( p1.getX(), p1.getY(), p1.getX(), x_axis );
                 getGraphics().drawString( Double.toString( mid ), p1.getX(), x_axis + 12);
                double tmp = f( mid );
                if( f( mid ) > 0 ) {
                    high = mid;
                }
                else {
                    low = mid;
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        bisearch bs = new bisearch();
        bs.setVisible(true);
    }
    
    private double low, high, mid;
    private double leftBound = 2.7, rightBound = 4.3, eps = 0.003;
    private double lowerBound, upperBound;
    private int x_axis, y_axis;
    Button nextButton;
}

class point {
    public point() {
        x = 0;
        y = 0;
    }
    public point(int _x, int _y) {
        x = _x;
        y = _y;
    }
    public int getX() { return x; }
    public int getY() { return y; }
    private int x;
    private int y;
}

太懒,不想把这段代码弄成applet了,想看编译后结果的同学点击这里下载可执行程序啊。

杂碎

  • cai组队的事纠结了。
  • 84路换车站了,昨天从教化桥的一头跑到另一头去坐公交,T.T。以后再也不坐84了。
  • 上周的大概把三天时间花在toolbox源码的调研上,到周日才搞清楚要做的应该是service grid。脑残了…
  • 事情太多,还需多多努力啊…
blog comments powered by Disqus