//c header
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include <stdlib.h>
//c++ header
#include <iostream>
#include <assert.h>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#include <fstream>
//linux header
#include <time.h>
using namespace std;
/////////////////problem1 start//////////////////////
/**
* problem1 description : input a string that ends with '!' from console
* and then output it in reverse
*/
void input(char* s)
{
char ch = (char)getchar();
if(ch != '!'){
*s = ch;
input(s+1);
}
else
*s = '\0';
}
void rstring(char* s,int n)
{
while(n--){
printf("%c",*(s+n));
}
printf("\n");
}
void p1()
{
char *a = (char*)malloc(sizeof(char)*1000);
input(a);
printf("reverse string : \n");
rstring(a,strlen(a));
free(a);
}
///////////////problem1 end///////////////////////////
///////////////problem2 start/////////////////////////
/**
* problem2 description : all arrangement problem
*/
/**
* output stack data type
*/
ostream& operator <<(ostream &out,const stack<int,vector<int> > &S)
{
stack<int,vector<int> > tmp = S;
int size = (int)tmp.size();
for(int i=0;i<size;i++){
cout << tmp.top() << " ";
tmp.pop();
}
cout << endl;
return out;
}
/**
* copy whole array elements except src[delIndex]
* For example, when src : {1,2,3,4}, delIndex : 2, n: 4
* then the dest : 1,2,4
**/
void copyArray(int* src,int delIndex, int n, int* dest)
{
assert(src != NULL && dest != NULL);
int j = 0;
for(int i=0;i<n;i++){
if(i == delIndex)
continue;
dest[j++] = src[i];
}
}
static stack<int,vector<int> > S;
static int size = 0;
//method 1
void arrange1(int* ptr,const int n)
{
if(1 == n){
S.push(*ptr);
cout << "the " << ++size << "-th :";
cout << S;
S.pop();
return;
}
for(int i=0;i<n;i++){
S.push(*(ptr+i));
int *ptr_ = new int [n-1];
copyArray(ptr,i,n,ptr_);
arrange1(ptr_,n-1);
S.pop();
delete [] ptr_;
}
}
//method 2
void arrange2(int *ptr,const int n,bool *isUsed)
{
if((unsigned int)S.size() == n){
cout << "# " << ++size << " :";
cout << S;
return;
}
for(int i=0;i<n;i++)
if(!isUsed[i]){
isUsed[i] = true;
S.push(ptr[i]);
arrange2(ptr,n,isUsed);
S.pop();
isUsed[i] = false;
}
}
void p2()
{
const int N = 6;
int a[N] = {1,2,3,4,5,6};
bool isUsed[N] = {false};
clock_t begin = clock();
// arrange2(a,N,isUsed);
arrange1(a,N);
clock_t end = clock();
cout << "time consumed : " << begin - end << endl;
}
template<class T>
void printArray(T *ptr, int n)
{
for(int i=0;i<n;i++)
cout <<*(ptr+i) << " ";
cout << endl;
}
///////////////problem2 end///////////////////////////
///////////////problem3 start/////////////////////////
/**
* problem3 description : we have some goods that weights w1,w2,w3,....we use a bag which maximum volume is T.
* output all possible conditions that satisfy w1+w2+...=T
*/
/**
* judge whether array T has the element t, where n is the total number of elements in array
*/
template <class T>
bool isIn(const T *array, int n, const T &t)
{
assert(array != NULL);
for(int i=0;i<n;i++)
if(array[i] == t)
return true;
return false;
}
template <class T>
void printVec(const vector<T> &v, const char sep = ' ')
{
for(int i=0;i<v.size();i++)
cout << v[i] << sep;
cout << endl;
}
int sumVec(const vector<int> &s)
{
int sum = 0;
int size = (int)s.size();
for(int i=0;i<size;i++)
sum += s[i];
return sum;
}
//static int num = 0; //the number of answers
//save the answers
static vector<int> SS;
static set<vector<int> > ans;
void solveP3(int *w,const int N,int T)
{
if(0 == N) return;
for(int i=0;i<N;i++){
SS.push_back(*(w+i));
if(sumVec(SS) == T){
vector<int> SS_ = SS;
sort(SS_.begin(),SS_.end());
ans.insert(SS_);
// cout << ++num << "-th answer : ";
// printVec(SS);
SS.pop_back();
continue;
}
int *w_ = new int [N-1];
copyArray(w,i,N,w_);
solveP3(w_,N-1,T);
SS.pop_back();
delete [] w_;
}
}
void p3()
{
const int N = 10;
int w[N];
int T;
int nTimes = 0;
cout << "please input the weight of " << N << " packages :" << endl;
for(int i=0;i<N;i++)
cin >> w[i];
cout << "please input the maximum volume of the bag :" << endl;
cin >> T;
solveP3(w,N,T);
set<vector<int> >::iterator it;
cout << "finally result : " << endl;
for(it = ans.begin();it != ans.end();it++){
cout << ++nTimes << "-th answer : ";
printVec(*it);
}
}
///////////////problem3 end///////////////////////////
///////////////probelm4 start/////////////////////////
/**
* problem4 description : prime ring problem. Use number from 1 to 20 to fill 20 positions and ensure
that the sum of two adjacent number is prime. These 20 positions form a ring.
*/
static vector<int> ring; // data in ring
static vector<int> org; // original data set
static bool isFind = false; //isFind : a sign that indicate if the solution is found
// decide whether a number is a prime
bool isPrime(const int v)
{
for(int i=2;i<=sqrt(v);i++)
if(v%i == 0)
return false;
return true;
}
//try next position
void tryPos1(int pos)
{
if(isFind)
return;
for(int i=0;i<org.size();i++)
if(isPrime(org[i]+ring[ring.size()-1])){
int tmp = org[i];
ring.push_back(tmp);
org.erase(org.begin()+i);
if(pos == 20){
if(isPrime(ring[ring.size()-1]+ring[0])){
printVec(ring);
isFind = true;
}
ring.pop_back();
org.insert(org.begin()+i,tmp);
return;
}
tryPos1(pos+1);
ring.pop_back();
org.insert(org.begin()+i,tmp);
}
}
void tryPos2(int pos, bool *isUsed)
{
if(isFind)
return;
for(int i=0;i<org.size();i++)
if((!isUsed[i])&&isPrime(org[i]+ring.back())){
ring.push_back(org[i]);
isUsed[i] = true;
if(20 == pos){
if(isPrime(ring.back()+ring.front())){
printVec(ring);
isFind = true;
}
ring.pop_back();
isUsed[i] = false;
return;
}
tryPos2(pos+1,isUsed);
ring.pop_back();
isUsed[i] = false;
}
}
void p4()
{
const int N = 20;
bool isUsed[N-1];
for(int i=1;i<=N;i++){
org.resize(0);
ring.resize(0);
for(int j=1;j<=20;j++)
if(j != i)
org.push_back(j);
ring.push_back(i);
isFind = false;
memset((void*)isUsed,false,sizeof(isUsed));
// tryPos1(2);
tryPos2(2,isUsed);
}
}
///////////////problem4 end///////////////////////////
///////////////problem5 start/////////////////////////
/**
* problem5 description : Given number from 1 to N,output all possible combinations that contain r numbers
*/
static vector<int> V;
static int size5 = 0;
void combination1(int* s,const int N, const int r)
{
if(V.size() == (unsigned int)r){
cout << "#" << ++size5 << " : ";
printVec(V);
return;
}
for(int i=0;i<N;i++){
V.push_back(s[i]);
int* s_ = new int [N-1];
copyArray(s,i,N,s_);
combination1(s_,N-1,r);
V.pop_back();
delete [] s_;
}
}
void combination2(int *s, int indexStart, const int N, const int r)
{
if((unsigned int)V.size() == r){
cout << "#" << ++size5 << " : ";
printVec(V);
return;
}
for(int i = indexStart;i<N;i++){
V.push_back(s[i]);
combination2(s,i+1
,N,r);
V.pop_back();
}
}
void p5()
{
const int N = 10;
const int r = 9;
int* data = new int [N];
for(int i=1;i<=N;i++)
*(data+i-1) = i;
combination2(data,0,N,r);
delete [] data;
}
///////////////problem5 end///////////////////////////
///////////////problem 6 start////////////////////////
/*
* problem 6 description : decompose a given number to the sum of some numbers that are smaller than itself.
*/
static
alg.cpp.tar.gz_全组合
版权申诉
90 浏览量
2022-09-19
21:33:21
上传
评论
收藏 10KB GZ 举报
我虽横行却不霸道
- 粉丝: 75
- 资源: 1万+
最新资源
- sap-me-nonconformance-how-to-guide-en.pdf
- sap-me-nonconformance-how-to-guide-en.pdf
- MSI3401-VB一款SOT23封装P-Channel场效应MOS管
- sap-me-mobile-how-to-guide-en.pdf
- 策略模式代码示例 Java版
- Distilling Step-by-Step与DIT.pdf
- 汉诺塔(Tower of Hanoi)python.pdf
- sap-me-message-board-how-to-guide-en.pdf
- MSI3400-VB一款SOT23封装N-Channel场效应MOS管
- sap-me-labor-tracking-how-to-guide-en.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈