大家好，又见面了，我是你们的朋友全栈君。
NOIP2011普及组初赛
15
现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、200。那么，“也”字的编码长度是（ 3）。 解析：如图所示
23
代码语言：javascript复制#include <iostream>
using namespace std;
int main(){
int i, n, m, ans;
cin>>n>>m;
i = n;
ans = 0;
while (i <= m){
ans = i;
i ;
}
cout<<ans<<endl;
return 0;
}输入： 10 20 输出： 165 解析：根据对程序的理解，求10~20的和即可
24
代码语言：javascript复制#include <iostream>
#include <string>
using namespace std;
int main(){
string map = "22233344455566677778889999";
string tel;
int i;
cin>>tel;
for (i = 0; i < tel.length(); i )
if ((tel[i] >= '0') && (tel[i] <= '9'))
cout<<tel[i];
else if ((tel[i] >= 'A') && (tel[i] <= 'Z'))
cout<<map[tel[i] - 'A'];
cout<<endl;
return 0;
}输入：
CCF-NOIP-2011
输出：
22366472011
解析：如果输入的字符是大写字母，就按照字母的顺序在map中找到相对应的数字。如果输入的字符为数字，直接输出即可。
28
（大整数开方）输入一个正整数n(1≤n＜10100)，试用二分法计算它的平方根的整数部分。
代码语言：javascript复制#include <iostream>
#include <string>
using namespace std;
const int SIZE = 200;
struct hugeint {
int len, num[SIZE];
};
//其中 len 表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推
hugeint times(hugeint a, hugeint b) {
//计算大整数 a 和 b 的乘积
int i, j; hugeint ans;
memset(ans.num, 0, sizeof(ans.num));
for (i = 1; i <= a.len; i )
for (j = 1; j <= b.len; j )
① = a.num[i] * b.num[j];
for (i = 1; i <= a.len b.len; i ) {
ans.num[i 1] = ans.num[i] / 10;
②;
}
if (ans.num[a.len b.len] > 0)
ans.len = a.len b.len;
else
ans.len = a.len b.len - 1;
return ans;
}
hugeint add(hugeint a, hugeint b){
//计算大整数 a 和 b 的和
int i; hugeint ans;
memset(ans.num, 0, sizeof(ans.num));
if (a.len > b.len)
ans.len = a.len;
else
ans.len = b.len;
for (i = 1; i <= ans.len; i ) {
ans.num[i] =③;
ans.num[i 1] = ans.num[i] / 10;
ans.num[i] %= 10;
}
if (ans.num[ans.len 1] > 0) ans.len ;
return ans;
}
hugeint average(hugeint a, hugeint b){
//计算大整数 a 和 b 的平均数的整数部分
int i; hugeint ans;
ans= add(a, b);
for(i = ans.len; i >= 2; i--) {
ans.num[i - 1] = (④) * 10;
ans.num[i] /= 2;
}
ans.num[1] /= 2;
if (ans.num[ans.len] == 0) ans.len--;
return ans;
}
hugeint plustwo(hugeint a) {
//计算大整数 a 加 2 后的结果
int i; hugeint ans;
ans = a;
ans.num[1] = 2;
i = 1;
While ((i <= ans.len) && (ans.num[i] >= 10)) {
ans.num[i 1] = ans.num[i] / 10;
ans.num[i] %= 10;
i ;
}
if (ans.num[ans.len 1] > 0)⑤;
return ans;
}
bool over(hugeint a, hugeint b){
//若大整数 a>b 则返回 true，否则返回 false
int i;
if (⑥) return false;
if (a.len > b.len) return true;
for (i = a.len; i >= 1; i--) {
if (a.num[i] < b.num[i])return false;
if (a.num[i] > b.num[i]) return true;
}
return false;
}
int main(){
string s;
int i;
hugeint target, left, middle, right;
cin>>s;
memset(target.num, 0, sizeof(target.num));
target.len = s.length();
for (i = 1; i <= target.len; i )
target.num[i]= s[target.len - i] - ⑦;
memset(left.num, 0, sizeof(left.num));
left.len = 1;
left.num[1] = 1;
right = target;
do {
middle = average(left, right);
if (over(⑧))right = middle;
else left = middle;
} while (!over(plustwo(left), right));
for (i = left.len; i >= 1; i--)
cout<<left.num[i];
cout<<endl;
return 0;
}解析：空①，分别将乘数的第i位和第j位相乘，所以应填入乘积的i j-1位。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
