01背包问题-回溯法-C语言实现。

01背包问题-回溯法

?View Code C
#include <stdio .h>
#include <stdlib .h>
 
int n=5,c=10;
int value[5]={6,3,5,4,6};
int weight[5]={2,2,6,5,4};
int cv[5]={0,0,0,0,0};
int bv[5]={0,0,0,0,0};
int cw=0;
int curv = 0 ;
int bestv =0 ;
void output()
{
   int i =0;
   for(i; i<n ; i++)
     printf("%d ",bv[i]);
   printf("%d",bestv);     
}
 
void trackback(int i)
{
     int j;
    if(i>=n)
    {
         if(bestv<curv ) 
        {
            for(j=0;j<n;j++)
                bv[j] = cv[j]; 
            bestv = curv;
        } 
    }
    else
    {
         if(cw + weight[i]<=c)
         {
          cv[i] = 1; 
          cw +=weight[i];
          curv+= value[i];
          trackback(i+1);
          cw -=weight[i];
          curv-= value[i];
          }
          cv[i] =0;
          trackback(i+1);
 
    }
 
 
}
int main(int argc, char *argv[])
{
  trackback(0);
  output();
  system("PAUSE");	
  return 0;
}

不要让自己的习惯称为左右自己的思维

开学后复习的第一门课程是C语言，选择翻看这本经典的《c  programming language 》。目前看到第三章3.3。书中介绍了两种用C语言实现的折半查找法。看到第一个算法的时候自己感觉很容易理解，随即向后看去，后面的一道习题，让用另外的一种策略来实现改进现有的折半查找，要求只用一次判断来实现，实验比较一下这两个算法的执行效率上是否存在差异。此时心想着这一定是一个比前面那个更高明的算法，于是乎，兴奋的去翻看了答案，看着答案的实现感觉理解起来还行，代码比原有的长，比原来的逻辑复杂。心想着，这就是高明的算法的啊。谁知道后面的解析对答案的评价是：“两种方案的执行时间几乎没有什么差异。我们并没有得到多大的性能改进，反而失掉了代码可读性。教材原有的代码更容易阅读和理解”。

看到这句话后，立马有一种被欺骗的感觉，我上当了。可仔细想想，这难道不是因为我自己的意识在作怪吗。自己干嘛不亲自将两种代码都做做实验呢。做个test，看看两种方法的执行时间的话，也许自己会确定自己的答案。永远不要跟着自己的习惯走，让自己认为答案永远都是好的。有时候自己动动手，会有更大的收获。自己最近想的太多了，可是动手的时间少了。平衡一下自己的实践和理论学习也是必须的。

下面我把两段代码都写出来共大家参考，也算是一次练手的机会吧。

?View Code C
int binsearch(int x ,int v[],int n)
{
    int low ,high,mid;
    low =0 ;
    high=n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(xv[mid])
            low=mid+1;
      else
            return mid;
    }
     return -1;
}
?View Code C
int binsearch(int x ,int v[],int n ) 
{
	int low ,high ,mid;
	low = 0 ;
	high = n-1;
	mid = (low+high)/2;
	while(low< =high&&x!=v[mid])
	{
	  if(x<v[mid])
	     high=mid+1;
	  else
	     low = mid-1;
	  mid = (low+high)/2;
	}
	if(x==v[mid])
	  return mid;
	else 
	  return -1;
}

[转]c# 多线程 编程

一.多线程的概念

Windows是一个多任务的系统，如果你使用的是windows 2000及其以上版本，你可以通过任务管理器查看当前系统运行的程序和进程。什么是进程呢？当一个程序开始运行时，它就是一个进程，进程所指包括运行中的程序和程序所使用到的内存和系统资源。而一个进程又是由多个线程所组成的，线程是程序中的一个执行流，每个线程都有自己的专有寄存器(栈指针、程序计数器等)，但代码区是共享的，即不同的线程可以执行同样的函数。多线程是指程序中包含多个执行流，即在一个程序中可以同时运行多个不同的线程来执行不同的任务，也就是说允许单个程序创建多个并行执行的线程来完成各自的任务。浏览器就是一个很好的多线程的例子,在浏览器中你可以在下载JAVA小应用程序或图象的同时滚动页面,在访问新页面时,播放动画和声音,打印文件等。

Continue reading →

进程、线程与应用程序域(AppDomain) 浅析

进程
进程是操作系统用于隔离众多正在运行的应用程序的机制。在．Net之前，每一个应用程序被加载到单独的进程中，并为该进程指定私有的虚拟内存。进程不能直接访问物理内存，操作系统通过其它的处理把这些虚拟内存映射到物理内存或IO设备的某个区域，而这些物理内存之间不会有重叠，这就决定了一个进程不可能访问分配给另一个进程的内存。相应地，运行在该进程中的应用程序也不可能写入另一个应用程序的内存，这确保了任何执行出错的代码不会损害其地址空间以外的应用程序。在这种机制下，进程作为应用程序之间一个独立而安全的边界在很大程度上提高了运行安全。

Continue reading →

一摞烙饼引发的“血案”

看移山之道这个网站，看到了不错的问题，好多牛人在讨论，以后得常去，最近忙着考试，写到要少的多了。

有一次我烙了三个饼，一个两面都焦了，一个两面都是金黄色，一个一面是焦的，一面是金黄色，我把它们摞一起，只能看到最上一面，发现是焦的，问最上面这个饼的另一面是焦的概率是多少？

解法1：

1. 最上一面是焦的, 排除最上一张是两面金黄色

2. 剩下两张饼四个面, 三面是焦的, 一面金黄色, 现知道其中一面是焦的,

所以判断另一面是焦的概率就是求 二面焦 + 一面金黄 中焦的概率, = 2/2+1 = 2/3

解法2：

A=最上面的饼双面焦

B=最上面的饼双面金黄

C=最上面的饼一面金黄一面焦

J=最上面的一面焦

则P(J|A)=1，P(J|B)=0，P(J|C)=0.5

P(A|J)=P(AJ)/P(J)=(1/3)/(1/2)=2/3