`
mmdev
  • 浏览: 12845575 次
  • 性别: Icon_minigender_1
  • 来自: 大连
文章分类
社区版块
存档分类
最新评论

【编程珠玑】第三章 数据决定程序结构

 
阅读更多

一,内容

通过使用恰当的数据结构来替代复杂的代码。

二,习题

1、题目描述:本书出版之时,美国的个人收入所得税分为5种不同的税率,其中最大的税率大约为40%.以前的情况则更为复杂,税率也更高。下面所示的程序文本采用25个if语句的合理方法来计算1978年的美国联邦所得税。税率序列为0.14, 0.15, 0.16, 0.17, 0.18.....。序列中此后的计算大于0.01.有何建议呢?

if income <= 2200

tax = 0;

else if income <= 2700

tax = 0.14 * (income - 2200);

else if income <= 3200

tax = 70 + 0.15 * (income - 2700);

else if income <= 3700

tax = 145 + 0.16 * (income -3200);

else if income <= 4200

tax =225 + 0.17 * (income - 3700);

.......

else

tax =53090 + 0.70 * (income - 102200);

采用二分搜索定位到采用哪个分段函数,然后对应求出结果。

源码:

#include <iostream>
using namespace std;

int basetax[100];
int lowerbound[100];
double taxrate[100];

int search(int lowerbound[],int income)
{
	int i=0;
	int j=99;
	int t=(i+j)/2;
	
	while(1)
	{
		
		if(income - lowerbound[t] < 50 && income - lowerbound[t] >=0)
			return t;
		else if(income - lowerbound[t] < 0) //在左侧寻找 
			{
				j=t;
				t=(i+j)/2;
				
			}
		else
			{
				i=t;
				t=(i+j)/2;
			}			
	}	
	return  -1;
	
}
int main()
{
	basetax[0]=0;
	lowerbound[0]=0;
	taxrate[0]=0;
	
	basetax[1]=0;
	lowerbound[1]=2200;
	taxrate[1]=0.14;
	
	for(int i=2;i<100;++i)
	{
		basetax[i]=75*i-80;
		lowerbound[i]=2200 + (i-1)*500;
		taxrate[i]=(double)(14 + i-1)/100;
	
	}	
	
	if(search(lowerbound,salary))
	{
		int salary=2202;
		int j=search(lowerbound,salary);

		double tax= basetax[j] +   (double)taxrate[j]*(salary -lowerbound[j]);
	
		cout<<tax<<endl;
	}
	
	return 0;
}

2、

#include <iostream>
using namespace std;

int main()
{
	int t=0;
	int i,k;
    int  n=10;
 	int c[10]={1,2,3,4,5,6,7,8,9,10};
 	int a[10]={0};
	for(k=1;k<n;++k)
	{
    	for(i=1;i<k;++i)
       		a[k] = a[k-i] * c [i];

		a[k] +=c[k+1];
	}
	for(i=0;i<n;++i)
		cout<<a[i]<<endl;
	
	return 0;
}


3、当要输入数据很多,且没有规律时,可以考虑编写一个格式信函发生器(form letter generator)用于解析格式信函模板(form letter schema)。将数据从控制层分离的好处在于:避免每次针对不同的数据编写不同的代码;当需要改变一些公用文本的输出方式时,直接编辑模板即可,并不需要对数据进行修改

题目要求:输入一个字母,输出一个字符数组,该数组要以图像的方式将该字母的大写打印出来。
对于26个字母,每个字母的外形并没有必然规律可循,最直接方法是编写26个函数,针对特定的字母编写特定的打印程序,这是个体力活,代码数量将非常巨大。联想上面的格式信函编程,可以考虑为字母的外形设计一个定制模板,自己规定一套模板编写的格式,然后写一个解析程序,每次打印字母时,只需解析字母对应的模板即可,这样主要的工作量就花在每个字母模板的编写上,当然模板的编写是相当简单的,将字母图形转化为相应的模板格式即可。例如: 一个字母可以利用length = 12, width = 9的矩阵来表示


x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
任何母都可以在这张表示出来,每个点就像一个像素点。下面就对字母I和L进行模板编码,编码要求
(1)用尽可能简单的方式表示上面的图像;
(2)方便程序解析;
(3)必须适用于所有的情况
根据书上给出的编码结构,上图可表示为:
39x
63b3x3b
39x
编码规则: 第一列表示要打印的行数,,后面的数字代表每行要打印的字符个数,个数后面紧跟要打印的字符,并用空格隔开。这里字母b表示空格。根据上述规则,字母L编码如下
93x6b
39x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x
x

4、日期处理

这里把所有相关的处理函数放出来。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 
typedefstruct _date 
{
int year, month, day; 
}date;

//看是否是闰年
int leap(int year) 
{
return (0 == year % 4 && year % 100) || year % 400 == 0; 
}

//看是时间是否有效
int legal(date a) 
{
if (a.month <0 || a.month > 12) return 0; 
if (a.month == 2) return a.day > 0 && a.day <= (28 + leap(a.year)); 
return a.day >0 && a.day <= days[a.month -1]; 
}


//比较时间
int datecmp(date a, date b) 
{
if (a.year != b.year) return a.year - b.year; 
if (a.month != b.month) return a.month - b.month; 
return a.day - b.day; 
}


//计算周几?
int weekday(date a) 
{
inttm = a.month >= 3 ? (a.month - 2) : (a.month + 10); 
int ty = a.month >= 3 ? (a.year) : (a.year - 1); 
return (ty + ty/4 - ty/100 + ty/400 + (int)(2.6 * tm - 0.2) + a.day) % 7; 
}

//时间化为天数
int date2int(date a) 
{
int i ; 
int ret = a.year * 365 + (a.year - 1) / 4 - (a.year -1) / 100 + (a.year - 1) / 400; 
days[1] += leap(a.year);
for (i = 0; i < a.month - 1; ret += days[i++]); 
days[1] = 28;
return ret + a.day; 
}

//天数化为时间
date int2date(int a) 
{
date ret;
int i = 0; 
ret.year = a/146097*400;
for (a %= 146097; a >= 365+leap(ret.year); 
a -= 365 + leap(ret.year), ret.year++);
days[i] += leap(ret.year);
for (ret.month = 1; a >= days[ret.month - 1]; a -= days[ret.month - 1], ret.month++);
days[1] = 28;
ret.day = a + 1;
return ret; 
}

//计算距离
int dist(date a, date b) 
{
int ad = date2int(a); 
int bd = date2int(b); 
return ad - bd > ? ad - bd : bd - ad; 
}


//生成日历
void cal(date a) 
{
int i, w, j, k; 
a.day = 1;
if (a.month == 2) { k = days[a.month - 1] + leap(a.year);} 
else k = days[a.month - 1]; 

printf(" %2d月%4d年 \n", a.month, a.year);
printf("日 一 二 三 四 五 六\n");
w = weekday(a);
i = w % 7;while (i--) printf(" "); printf("%2d", 1); 
if (w % 7 == 6) printf("\n"); ++w; 

for (i = 1; i <= k; ++i, w = (w + 1) % 7) 
{
if (w % 7 == 0) printf("%2d", i); 
else printf(" %2d", i); 
if (w % 7 == 6) printf("\n");
}
}



第5题,解法是hash表中带hash。第一个以ic, tic 等做hash

首先根据后缀找到hash_set,再把余下的字段,依次在hash_set中查找,并取出最长的。

#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iterator>
#include<iostream>
#include<algorithm>
#include<hash_map>
#include<hash_set>

usingnamespace std; 
usingnamespace stdext; 

char *p[] = {"et-ic","al-is-tic","s-tic","p-tic","-lyt-ic","ot-ic","an-tic",
"n-tic","c-tic","at-ic","h-nic","n-ic","m-ic","l-lic","b-lic","-clic","l-ic",
"h-ic","f-ic","d-ic","-bic","a-ic","-mac","i-ac"};


void build_map(hash_map<string, hash_set<string> >& dict) 
{
constint n = sizeof(p)/sizeof(char *); 
for (int i = 0; i < n; ++i) 
{
string line = p[i]; reverse(line.begin(), line.end());
int pos = line.find('-');
dict[line.substr(0, pos)].insert(line.substr(pos + 1, line.length() - pos - 1)); 
}
}

string lookup(hash_map<string, hash_set<string> >& dict, string word) 
{
string line = word; reverse(line.begin(), line.end());
int pos = line.find('-');
string ret;

hash_map<string, hash_set<string> >::iterator iter;
if (dict.end() != (iter = dict.find(line.substr(0, pos)))) 
{
hash_set<string> &h = iter->second;
string temp = line.substr(pos + 1, line.length() - pos - 1); 
for (int j = 1; j <= temp.length(); ++j) 
{
string c = temp.substr(0, j);
if (h.find(c) != h.end() && c.length() > ret.length()) 
ret = c;
}
}
ret = iter->first +"-" + ret;
reverse(ret.begin(), ret.end());
return ret; 
}
int main(void)
{
string sline;
hash_map<string, hash_set<string> > dict;
build_map(dict);

while (cin >> sline) 
{
cout << lookup(dict, sline) << endl;
}
return 0; 
}



6、这个可以用python来写,下面先看一下示例代码。

模板文件/tmp/win03.domain.template

[python] view plaincopy;SetupMgrTag
[Unattended]

[GuiUnattended]
AdminPassword=${admin_password}
EncryptedAdminPassword=NO

OEMSkipRegional=1

[UserData]
ComputerName=${computer_name}



代码

[python] view plaincopyimport os 

Template =None
if Template isNone:
t = __import__('Cheetah.Template', globals(), locals(), 
['Template'], -1)
Template = t.Template

fp = open('/tmp/unattend.xml','w')
tem = open('/tmp/win03.domain.template').read()
domain_list = {'computer_name':'computer',
'admin_password':'admin',
'Use':'Use'}
info = str(Template(tem, searchList=[domain_list]))
fp.write(info)
fp.close()


如果采用C++实现,并且${}里面的代单词表明是要被替换的单词。那么处理方法如下:

[python] view plaincopyvoid Template(char *fname, char *temp_fname, map<string, string>& dict) 
{
ofstream output(fname);
ifstream temp(temp_fname);
string line;
while (getline(temp, line, '\n'))
{
int bpos =0;
string::size_type pos =0;
while (string::npos != (pos = line.find("${", bpos))) 
{
string::size_type epos = line.find("}", pos); 
string t = line.substr(pos +2, epos - pos -2);
cout << t << endl;
map<string, string>::iterator iter = dict.find(t);
if (dict.end() != iter) 
{
line.replace(pos, epos - bpos +1, iter->second);
bpos += iter->second.length();
}
else
{
bpos = epos +1;
}
}
output << line <<"\n\r";
}
temp.close();
output.close();
}



7、略去,比较扯

8、2^16 = 65536个数。所以5个七段显示器肯定是够用的。

因为最大的数 65535 有五位数。

#include <iostream>
#include <memory>
using namespace std;

void  showNumber(int i)
{
	int j=i;
	switch(j)
	{
		case 0:printf(" --\n");break;
		case 1:printf("|");break;
		case 2:printf("  |\n");break;
		case 3:printf(" --\n");break;
		case 4:printf("|");break;
		case 5:printf("  |\n");break;
		case 6:printf(" --\n");break;
		default :break; 
	};
}
void  showNullNumber(int i)
{
	switch(i)
	{
		case 0:printf("\n");break;
		case 1:printf(" ");break;
		case 2:printf("   \n");break;
		case 3:printf("");break;
		case 4:printf(" ");break;
		case 5:printf("   \n");break;
		case 6:printf("\n");break;
		default :break; 
	};
}

void GraphFigure(int i)
{
	int show[7];
	int show0[]={1,1,1,0,1,1,1};
	int show1[]={0,1,0,0,1,0,0};
	int show2[]={1,0,1,1,1,0,1};
	int show3[]={1,0,1,1,0,1,1};
	int show4[]={0,1,1,1,0,1,0};
	int show5[]={1,1,0,1,0,1,1};
	int show6[]={1,1,0,1,1,1,1};
	int show7[]={1,0,1,0,0,1,0};
	int show8[]={1,1,1,1,1,1,1};
	int show9[]={1,1,1,1,0,1,1};
	
	
	switch(i)
	{
		case 0:memcpy(show,show0,sizeof(show));break;
		case 1:memcpy(show,show1,sizeof(show));break;
		case 2:memcpy(show,show2,sizeof(show));break;
		case 3:memcpy(show,show3,sizeof(show));break;
		case 4:memcpy(show,show4,sizeof(show));break;
		case 5:memcpy(show,show5,sizeof(show));break;
		case 6:memcpy(show,show6,sizeof(show));break;
		case 7:memcpy(show,show7,sizeof(show));break;
		case 8:memcpy(show,show8,sizeof(show));break;
		case 9:memcpy(show,show9,sizeof(show));break;
		default :break; 
	};
	for(int i=0;i<7;++i)
	{
		if(1 == show[i])
			showNumber(i);
		else
			showNullNumber(i);
	}

}
int main()
{
   for(int i=0;i<10;++i)
   {	
       GraphFigure(i);
       cout<<"\n\n";
   	
   }
	return 0;
}


分享到:
评论

相关推荐

    编程珠玑 算法 数据结构

    编程珠玑 很好的资料 能加强对对算法和数据结构的理解

    编程珠玑源码下载编程珠玑书后源代码

    编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码

    编程珠玑 编程珠玑 编程珠玑 编程

    我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑

    编程珠玑编程珠玑

    编程珠玑编程珠玑

    编程珠玑之第二章questionC 测试数据

    本资源只是“编程珠玑之第二章questionC: 求变位词问题”的简单的测试数据。

    编程珠玑 编程珠玑续

    编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充

    编程珠玑(续)

    《编程珠玑(续)》是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,...

    编程珠玑 第二版 修订版

    第3章 数据决定程序结构 21 3.1 一个调查程序 21 3.2 格式信函编程 23 3.3 一组示例 25 3.4 结构化数据 26 3.5 用于特殊数据的强大工具 27 3.6 原理 28 3.7 习题 29 3.8 深入阅读 30 第4章 编写正确的程序...

    编程珠玑续本

    编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本

    编程珠玑 第2版 kindle格式电子书

    编程珠玑 第2版 azw3格式电子书,适合kindle阅读 Jon Bentley是位于新泽西州Murray Hill的朗讯贝尔实验室计算机科学研究中心的技术委员会委员,Jon自1998年就成为Dr. Dobb's Joumal杂志的特约编辑,他的“编程珠玑”...

    编程珠玑及其源码

    编程珠玑,编程珠玑续以及源码,本书针对程序设计人员探讨了一系列的实际问题,这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨...

    编程珠玑高清pdf版.pdf

    编程珠玑高清pdf版.pdf

    编程珠玑高清pdf版

    编程珠玑高清pdf版,本书是计算机科学方面的经典名著《编程珠玑》的姊妹篇,讲述了对于程序员有共性的知识。网友提供

    编程珠玑习题集锦

    书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程...《编程珠玑(第2版)》是计算机科学方面的经典名著。

    编程珠玑.pdf

    第3章 程序员的忏悔 23 3.1 二分搜索 24 3.2 选择算法 26 3.3 子程序库 28 3.4 原理 30 3.5 习题 31 第4章 自描述数据 33 4.1 名字—值对 33 4.2 记录来历 36 4.3 排序实验 37 4.4 原理 39 4.5 习题 39 第二部分 实 ...

    《编程珠玑》源代码

    《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...

    编程珠玑+续

    编程珠玑+续

    编程珠玑总结笔记

    编程珠玑是一本提升coding能力不可多得的好书,看书时,可以结合这个笔记,突出重点。

Global site tag (gtag.js) - Google Analytics