[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战

[此贴子已经被作者于2007-6-16 16:32:25编辑过]

#include <iostream>
#include <stack>

using namespace std;

int main()
{
char digit[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

cout <<"输入待转换整数: ";
int number;
cin >>number;
cout <<endl;

cout <<"转换成多少进制? ";
int base;
cin >>base;
cout <<endl;

stack<char> stk;
char remain;
while (number!=0)
{
remain = digit[number%base];
stk.push(remain);
number /= base;
}

cout <<"结果: ";
while(!stk.empty())
{
cout <<stk.top();
stk.pop();
}
cout <<endl;
return 0;
}


第五题的,望指点!

版本2 ： 无迭代改进版本：


[CODE]
//file : queens.h
#pragma once
const int max_board_size = 24;
class queens{
public:
//constructor
queens(int size);

//main function
void solution(); //recursive function for backtracking
//times of solutions
static unsigned int times_of_solution;
protected:
//member functions
void print() const; //print the solution
void insert(int col); //add a queen the posn
void remove(int col); //delete a queen at row-1
bool isSolved() const; //return true if all queens at right posn
bool isUnguarded(int col) const; //return true if the posn is guarded by a queen
private:
//make bool array for the chessboard
bool col_free[max_board_size];
bool upward_free[2*(max_board_size-1)];
bool downward_free[2*(max_board_size-1)];
int queen_in_rows[max_board_size]; //store the column of queens at each row
//data members
int row;
int board_size;
};[/CODE]

[CODE]
//file : queens.cpp
#include "queens.h"
#include <iostream>
queens::queens(int size){
board_size = size;
row = 0;
//set all columns free
for (int i = 0;i < board_size;++i)
col_free[i] = true;
//set all upward diagonals free
for (int i = 0;i < 2*(board_size-1);++i)
upward_free[i] = true;
//set all downward diagonals free
for (int i = 0;i < 2*(board_size-1);++i)
downward_free[i] = true;
}
bool queens::isSolved() const{
return row == board_size;
}
bool queens::isUnguarded(int col) const{
return col_free[col] && upward_free[row+col]
&& downward_free[row-col+board_size-1];
}
void queens::insert(int col){
queen_in_rows[row] = col;
//set the column & diagonal which is guarded by queen to false
col_free[col] = false;
upward_free[row+col] = false;
downward_free[row-col+board_size-1] = false;
++row;
}
void queens::remove(int col){
//remove a queen at previous row
--row; //back to previous row
//set the column & diagonal which is guarded by queen to true
col_free[col] = true;
upward_free[row+col] = true;
downward_free[row-col+board_size-1] = true;
}
void queens::print() const{
for (int i = 0;i < board_size;++i){
for (int j = 0;j < board_size;++j)
std::cout << (j == queen_in_rows[i] ? "1 " : "0 ");
std::cout << std::endl;
}
std::cout << "---------------------------------" << std::endl;
++times_of_solution;
}
void queens::solution(){
if (isSolved())
print();
else
for (int col = 0;col < board_size;++col)
if (isUnguarded(col)){
insert(col);
//the steps for backtracking
solution();
remove(col);
}
}[/CODE]

[此贴子已经被作者于2007-6-16 13:10:49编辑过]

第五题用堆栈的话就有些限制了吧? 遇到堆栈很小的情况.
如果要考虑负数的话就更难了..象2,8,16等进制都是用补码表示的...啊..好难啊...

[此贴子已经被作者于2007-6-16 14:27:53编辑过]

很久没来了,现在C++板块弄的蛮不错的...大家继续加油. 路过顺便挑个简单的做做 呵呵

-----------------------------------------------------------------------------------------------------
17. 编写一个程序，当输入不超过６０个字符组成的英文文字时，计算机将这个句子
中的字母按英文字典字母顺序重新排列，排列后的单词的长度要与原始句子中的长度
相同。例如：

输入：

ＴＨＥ ＰＲＩＣＥ ＯＦＢＲＥＡＤ ＩＳ ￥１ ２５ ＰＥＲ ＰＯＵＮＤ

输出：

ＡＢＣ ＤＤＥＥＥ ＥＦＨＩＩＮＯ ＯＰ ￥１ ２５ ＰＰＲ ＲＲＳＴＵ

并且要求只对Ａ到Ｚ的字母重新排列，其它字符保持原来的状态。

程序代码：

[此贴子已经被作者于2007-6-17 10:38:17编辑过]

新手...有点看不懂.

仿佛是第六题吧!帮忙看一下,如果有冗余的地方还望多提点一下
希望看起不会太痛苦! --VC6.0
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

int main()
{
cout <<"Enter a number : ";
int number;
cin >>number;
int total = number * number;
int i = 0;
int j = 0;
//(1):
for (i = 0 ; i < number ; ++i)
{
for (j = 0 ; j < number ; ++j)
{
cout <<setw(5)<<total;
total -= 1;
}
cout <<endl;
}
cout <<endl;

//(2)
i = 0;
j = 0;
int num = 1;
vector< vector<int> > a;
a.resize(number);
for (int x = 0; x < number; ++x)
a[x].resize(number);
while(num <= number * number)
{
if(i == 0 || j == number)
{
if(j == number){
i+=1;
j--;
}
for(; j >= 0 && i != number; --j){
a[i][j] = num;
num++;
i++;
}
++j;
}
else if (j == 0 || i == number)
{
if (i == number){
j+=1;
i--;
}
for(; i >= 0 && j != number; --i){
a[i][j] = num;
num++;
j++;
}
++i;
}

}
for ( i = 0 ; i < number ; ++i)
{
for (int j = 0 ; j < number ; ++j)
cout <<setw(5)<<a[i][j];
cout <<endl;
}
cout <<endl;

帅就一个字！！！
呵呵

好像有些不对劲..
这里"若不平衡（如果仍然是左边重）则是b,或c偏重 / (如果是左边轻)则是d偏轻", 没有考虑到"e或f偏轻"的情况...
因为不能保证一定会把偏轻的那一个当成d拿到左边去(三选一)...所以分析时思路就被误导在"问题一定出在左边"上了.
之后再称已经没有意义了.

我个人认为, 3次只能找出假币, 要判断轻重必须称第4次.
假币判断方法:
1.左右各放2个, 平衡:剩下4个有假币; 不平衡:这4个有假币
2.在有假币的4个中, 取2个放上天平称, 平衡: 假币在剩下2个中; 不平衡:假币在这2个中
此时: 可以确定出A组:2个, 有假币; B组: 6个, 全部标准.
3.从A组取1个(标记A1), 和B组取1个标准硬币放到天平上比较.
平衡: 则A2为假币; 不平衡: A1为假币.

4.将假币与标准硬币做最后比较, 确定轻重.

都是牛人!
呵呵

NO.19:
Greedy Algorithms;

Analysis：
Remove item j from this load, the remaining load must be the

most valuable load weighing at most max - weight(j) that we can take from the n - 1 original items excluding j.
To solve the problem, we first compute the value per pound

value(i)/weight(i) for each item. Obeying a greedy strategy, we begins

by taking as much as possible of the item with the greatest value per

pound. If the supply of that item is exhausted and we can still carry

more, we takes as much as possible of the item with the next greatest

value per pound, and so forth until we can't carry any more. Thus, by

sorting the items by value per pound, the greedy algorithm runs in O(n

lg n) time.

#include<iostream>
using namespace std;
struct information
{
float price;
float weight;
float number;
int serial_number;
};
void sort_ascending(information good[],int n)// according to the ratio of price and weight,sort_ascending arrange
{
int i,j;
for(j=2;j<=n;j++)
{
good[0]=good[j];
i=j-1;
while(good[0].price>good[i].price)
{
good[i+1]=good[i];
i--;
}
good[i+1]=good[0];
}

}
void backpack(information good[],float max,int n)
{
float left;
int i,j;
for(i=1;i<n;i++)
good[i].number=0;
left=max;
for(i=1;i<n;i++)
{
if(good[i].weight>left)
break;
good[i].number=1;
left=left-good[i].weight;
}
if(i<=n)
good[i].number=left/good[i].weight;

for(j=2;j<n;j++) //according to good'serial number,from high to low
{
good[0]=good[j];
i=j-1;
while(good[0].serial_number<good[i].serial_number)
{
good[i+1]=good[i];
i--;
}
good[i+1]=good[0];
}
cout<<"The most excellent result is:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"The "<<i<<"th good should input: ";
cout<<good[i].number<<endl;
}
}
int main()
{
int i,j;
int n;
float max;
information *good;
while(j)
{
cout<<"Please input goods's number: "<<endl;
cin>>n;
good=new struct information [n+1];
cout<<"Please input the max of goods's capability"<<endl;
cin>>max;
cout<<endl;
int i;
for(i=1;i<=n;i++)
{
good[i].serial_number=i;
cout<<"Please input the "<<i<<"th goods'weight:"<<endl;
cin>>good[i].weight;
cout<<"Please input the "<<i<<"th goods'price:"<<endl;
cin>>good[i].price;
good[i].price=good[i].price/good[i].weight;
cout<<endl;
}
sort_ascending(good,n);
backpack(good,max,n);

break;
}
system("pause");
return 0;
}

[此贴子已经被作者于2007-6-19 11:31:34编辑过]

11. 巧排数字。将１、２、．．．、２０这２０个数排成一排，使得相邻的两个数之
和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。
--------------------------------------------------------------------------------------
[CODE]/*
title : NO.11
author : aipb2007
date : 2007-06-18

analysis :
It's problem like "N queen",both use the algorithm of recursion and backtracking.
Use an array to store the solution.

design :
//print one solution
print(int a[],int n);
//check an integer is already in the array
bool is_in(int a[],int n,int in);
//check a number is a prime number
bool is_prime(double num);
//recursive function for backtracking
void solution(int a[],int n,int k);

in addition:
The questions has a problem, it's so many solution for 20 numbers.By using this
way,the computer will use a large time to do this,maybe can not.
However,maybe my program has a low efficiency.
So I change the number to 8,just for testing.

sample output :
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
2 1 4 7 6 5 8 3
2 1 6 7 4 3 8 5
2 3 8 5 6 7 4 1
2 5 8 3 4 7 6 1
3 2 1 4 7 6 5 8
3 4 7 6 1 2 5 8
3 8 5 2 1 6 7 4
3 8 5 6 7 4 1 2
4 1 2 3 8 5 6 7
4 3 8 5 2 1 6 7
4 7 6 1 2 5 8 3
4 7 6 5 8 3 2 1
5 2 1 6 7 4 3 8
5 6 7 4 1 2 3 8
5 8 3 2 1 4 7 6
5 8 3 4 7 6 1 2
6 1 2 5 8 3 4 7
6 5 8 3 2 1 4 7
6 7 4 1 2 3 8 5
6 7 4 3 8 5 2 1
7 4 1 2 3 8 5 6
7 4 3 8 5 2 1 6
7 6 1 2 5 8 3 4
7 6 5 8 3 2 1 4
8 3 2 1 4 7 6 5
8 3 4 7 6 1 2 5
8 5 2 1 6 7 4 3
8 5 6 7 4 1 2 3
*/


#include <iostream>
#include <cmath>
using namespace std;
void print(int a[],int n){
for (int i = 0; i < n;++i)
cout << a[i] << " ";
cout << endl;
}

bool is_in(int a[],int n,int in){
for (int i = 0;i < n;++i)
if (in == a[i])
return true;
return false;
}

bool is_prime(double num){
double d = sqrt(num);
for (int i = 2;i <= (int)d;++i)
if ((int)num % i == 0)
return false;
return true;
}

void solution(int a[],int n,int k){
if (k == n && is_prime(a[k-2]+a[k-1]) && is_prime(a[0]+a[k-1]))
print(a,n);
else if (k < 2 || is_prime(a[k-2]+a[k-1])){
for (int i = 1;i <= n;++i)
if (!is_in(a,k,i)){
a[k] = i;
solution(a,n,k+1);
}
}
}

int main(){
int a[8];
solution(a,8,0);
}[/CODE]

[此贴子已经被作者于2007-6-18 19:27:26编辑过]

/*---------------------------------------------------------------------------
File name: C76-75.cpp
Author: HJin
Date: 6/18/2007

6/18/2007
-----------------------------------------------------------
1. Refine the analysis: provide optimal substructure and the
recurrence formula for c[p].

C76-75.cpp --- the cpp source file for solving the 75th of the 76
classical C/C++ problems.

经典 76 道编程题 之 75:

75. (钱币系统问题) 某钱币系统由 k (k≤20) 种硬币组成, 币值依次为 a[1],
a[2],...,a[k], 其中 a[i] (i=1,2,...,k) 为互不相同的正整数, 且依降序排列,
a[1]≤200. 给定某整数币值 n(n≤3000), 要求用最少枚数的硬币表示这个币值.
输入: 用文件输入已知数据, 格式为:
第 1 行: k (硬币种数)
第 2 行: a[1] a[2] ... a[k] (各币值用空格隔开,已按降序排列好)
第 3 行: n (给定的币值)
输出: 直接在屏幕上输出结果. 如果该钱币系统无法表示币值 n,应输出'No',
否则按以下格式输出:
第 1 行: 最少钱币枚数 r.
第 2 行: 输出若干形如 m*n 的表达式, m 为币值, n为使用该币值的枚数.
各式第 2 个因子之和应等于 r, 各式乘积之和应等于 n.
例: 设 (a[1],a[2],a[3])=(5,2,1), n=12, 则应输出
3
5*2 2*1.

Analysis:

1. If 1 is in the set { a[1], a[2], ..., a[k] }, then we can change
any number n in at most n cions (since n = 1*n);

2. There is some set { a[1], a[2], ..., a[k] } such that this coin
changing problem can be solved by a greedy algorithm. For exmaple,

{5, 2, 1}

is such a set. And there exists a set { a[1], a[2], ..., a[k] }
such that the greedy algorithm does not give an optimal soln. For
example,

{5, 4, 1}

is such a set: 8 = 5*1 + 1*3 is the greedy soln, which needs 4 cions,
whereas 8 = 4*2 tells us that we can use just 2 coins.

3. A dynamic programming algorithm exists for any set. This needs some
understanding of the topic. Cormen's book is a wonderful reference.

4. This is really a classical and an interesting problem and a lot of
references exist. Just google for "coin changing problem, dynamic programming".

5. This problem needs more analysis than programming efforts. A complete
soln of this problem needs to describe (and prove) the optimal substructure,
which we omitted.

6. Our soln does NOT fulfil the requirements described in the problem
statement.

7. The optimal substructure:

Write n = m + (n-m). Then the left half of an optimal soln for n must
be an optimal soln for m, the right half of the optimal soln for n must
be an optimal soln for n-m.

8. Let c[p] be the minimum number of coins to make change for n, then

c[p] = 0, if p = 0;
= 1 + min { 1 + c[ p-a[i] ]: a[i] <= p}, if p> 0

Sample output:

n=0, No
n=1, No
n=2, No
n=3, No
n=4, No
n=5, No
n=6, No
n=7, r=1: 7*1
n=8, No
n=9, No
n=10, No
n=11, No
n=12, No
n=13, No
n=14, r=2: 7*2
n=15, r=1: 15*1
n=16, No
n=17, No
n=18, No
n=19, No
n=20, No
n=21, r=3: 7*3
n=22, r=2: 15*1 7*1
n=23, No
n=24, No
n=25, No
n=26, No
n=27, No
n=28, r=4: 7*4
n=29, r=3: 15*1 7*2
n=30, r=2: 15*2
n=31, r=1: 31*1
n=32, No
n=33, No
n=34, No
n=35, r=5: 7*5
n=36, r=4: 15*1 7*3
n=37, r=3: 15*2 7*1
n=38, r=2: 31*1 7*1
n=39, No
n=40, No
n=41, No
n=42, r=6: 7*6
n=43, r=5: 15*1 7*4
n=44, r=4: 15*2 7*2
n=45, r=3: 15*3
n=46, r=2: 15*1 31*1
n=47, No
n=48, No
n=49, r=7: 7*7
n=50, r=6: 15*1 7*5
n=51, r=5: 15*2 7*3
n=52, r=4: 15*3 7*1
n=53, r=3: 15*1 31*1 7*1
n=54, No
n=55, No
n=56, r=8: 7*8
n=57, r=7: 15*1 7*6
n=58, r=6: 15*2 7*4
n=59, r=5: 15*3 7*2
n=60, r=4: 15*4
n=61, r=3: 15*2 31*1
n=62, r=2: 31*2
n=63, r=9: 7*9
n=64, r=8: 15*1 7*7
n=65, r=7: 15*2 7*5
n=66, r=6: 15*3 7*3
n=67, r=5: 15*4 7*1
n=68, r=4: 15*2 31*1 7*1
n=69, r=3: 31*2 7*1
n=70, r=10: 7*10
n=71, r=9: 15*1 7*8
n=72, r=8: 15*2 7*6
n=73, r=7: 15*3 7*4
n=74, r=6: 15*4 7*2
n=75, r=5: 15*5
n=76, r=4: 15*3 31*1
n=77, r=3: 15*1 31*2
n=78, r=10: 15*1 7*9
n=79, r=9: 15*2 7*7
n=80, r=8: 15*3 7*5
n=81, r=7: 15*4 7*3
n=82, r=6: 15*5 7*1
n=83, r=5: 15*3 31*1 7*1
n=84, r=4: 15*1 31*2 7*1
n=85, r=11: 15*1 7*10
n=86, r=10: 15*2 7*8
n=87, r=9: 15*3 7*6
n=88, r=8: 15*4 7*4
n=89, r=7: 15*5 7*2
n=90, r=6: 15*6
n=91, r=5: 15*4 31*1
n=92, r=4: 15*2 31*2
n=93, r=3: 31*3
n=94, r=10: 15*3 7*7
n=95, r=9: 15*4 7*5
n=96, r=8: 15*5 7*3
n=97, r=7: 15*6 7*1
n=98, r=6: 15*4 31*1 7*1
n=99, r=5: 15*2 31*2 7*1
Press any key to continue . . .

Reference:
1. Thomas H. Cormen, introduction to algorithms.

2. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#define INFPOS ~(1<<31) // (2^31-1)
#define DIM(x) (sizeof( (x) ) / sizeof( (x)[0] ))
using namespace std;

/**
@param a --- the array { a[1], a[2], ..., a[k] }. It does not
need to in decreasing order.
@param k --- number of coins
@param n --- the target number we want to make change
@return --- returns the minimum (positive) number of coins needed
to make a successful change; or -1 if the money system
cannot make the change.

Space complexity is Theta(n+k) --- there is a version of dynamic
programming algorithm which uses Theta(n*k) space. Obviously,
our version beats that version.
Time complexity is Theta(n * k).

Note that our algorithm does not require the set to be sorted beforehand.
*/
int change(int *a, int k, int n, bool print= true);

/**
print the optimal soln.
*/
int makeChange(int *a, int k, int n, int* b, bool print);

int main(int argc, char** argv)
{
//int a[] = {5, 4, 3};
int a[] = {15, 31, 7};
int k = DIM(a);
int n;
int res;

// test #1
for(n=0; n<100; ++n)
change(a, k, n);

// test #2
//for(n=40; n<80; ++n)
//{
// res = change(a, k, n, false);
// if(res == -1)
// cout<<n<<endl;
//}

return 0;
}

int change(int *a, int k, int n, bool print)
{
/**
c --- c[i] stores soln for n = i. If there is no soln for n=i,
then stores INFPOS;
s --- s[i] stores the index of the first coin for n=i. If there is
no soln for n =i, then stores INFPOS;
b --- b[j] stores the number of cions for the soln.
*/

int* c = new int[n+1];
int* s = new int[n+1];
int* b = new int[k];
int coinIndex=INFPOS;
int n2 = n;
int min;
int i;
int p;
int temp;

for(i=0; i<k; ++i)
b[i] = 0;

c[0] = 0; // n=0 needs zero coins to make
s[0] = INFPOS; // no coins can be used for n = zero

for(p=1; p<=n; ++p) // for face value 1 to n
{
min = INFPOS; // +\inf
for(i=0; i<k; ++i) // loop over the set of coins
{
if(a[i] <= p)
{
// temp implements the relation: 1 + +\inf = +\inf
temp = (c[p-a[i]] == INFPOS ? INFPOS : 1 + c[p-a[i]]);
if (min > temp )
{
min = temp; // keeps the local minimum
coinIndex = i; // select coin i
}
}
}

c[p] = min; // keeps the global min (the soln for n=p)
s[p] = coinIndex;
}

/**
build number of cions for each a[i] and store it in b[i]
*/
while(n2>0)
{
if( s[n2]>=0 && s[n2] <k )
++b[s[n2]];

n2 -= a[s[n2]];
}

// reuse n2 to keep a value
n2 = makeChange(a, k, n, b, print);

delete [] c;
delete [] s;
delete [] b;

return n2;
}

int makeChange(int *a, int k, int n, int* b, bool print)
{
int i;
int r=0;
int sum = 0;

if(print)
cout<<"n="<<n;

/**
calculate r --- the total number of cions for n
*/
for(i=0; i<k; ++i)
{
r+= b[i];
sum += b[i] * a[i];
}

/**
If the sum is not n, then there are no solns.
And treat the case n=0 as there are no solns.
*/
if (sum != n || n<1)
{
if(print)
cout<<", No"<<endl;
return -1;
}

if(print)
cout<<", r="<<r<<":\t";
for(i=0; i<k; ++i)
{
if( b[i] > 0 )
{
if(print)
cout<<a[i]<<"*"<<b[i]<<" ";
}
}

if(print)
cout<<endl;

return r;
}

[此贴子已经被作者于2007-6-19 3:01:51编辑过]