存档

文章标签 ‘C’

回溯法实现求24点的所有解 C版

2010年6月3日 没有评论

回溯法+递归

【问题描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。

您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：

若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。

阅读全文...

分类: 编程相关 标签: , ,

POJ 3280 Cheapest Palindrome C++版

2010年5月21日 没有评论

动态规划，回文数

阅读全文...

分类: 解题报告 标签: , ,

POJ 1163 The Triangle C版本

2010年5月20日 没有评论

动态规划，数学三角形

阅读全文...

分类: 解题报告 标签: , ,

重载+操作符 C++

2010年4月24日 没有评论

今天上c++课，老师讨论到的问题，在这里做下笔记

1
2
3
4
5
6
7
8
9
10
11
12
13

//comple.h
class comple
{
    friend comple operator+(const comple& lhs,const comple& rhs);
public:
    comple(void);
    comple(int);
    ~comple();
    comple(const comple& orig);
private:
    int real;
 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//comple.cpp
#include "stdafx.h"
#include <iostream>
#include "comple.h"
using namespace std;
comple::comple( void )
:real(0)
{
    cout<<this <<" of "<<this->real <<" constructor is called"<<endl;
 
}
 
comple::comple( int a)
:real(a)
{
    cout<<this <<" of "<<this->real<<" constructor is called"<<endl;
 
}
 
comple::comple( const comple& orig )
{
    cout<<this <<" of "<<orig.real<<" assignment is called"<<endl;
    this->real = orig.real;
}
comple::~comple()
{
    cout<<this <<" of "<<this->real<<" destructor is called"<<endl;
 
 
}
comple operator+(const comple& lhs,const comple& rhs)
{
    cout<< "operator+ is called"<<endl;
    comple a(lhs.real+rhs.real);
    return a;
}
1
2
3
4
5
6
7
8
9
10
11
12

//main.cpp
#include "stdafx.h"
#include "comple.h"
#include <iostream>
 
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    comple a(2);
    a+5;
    return 0;
}

程序输出

001CFB90 of 2 constructor is called
001CFAAC of 5 constructor is called
operator+ is called
001CFA70 of 7 constructor is called
001CFAB8 of 7 assignment is called
001CFA70 of 7 destructor is called
001CFAB8 of 7 destructor is called
001CFAAC of 5 destructor is called
001CFB90 of 2 destructor is called

解释下这个程序的执行过程：首先调用带int的构造函数，然后执行a+5时，编译器会自动调用带int的构造函数对5进行隐式转化。接下来调用operater+，在这个函数中实例化了一个匿名对象，并将该对象复制一份返回。该函数结束后销毁局部栈上的变量，首先销毁复制的实例，再销毁匿名实例（先进后出）。程序结束后，销毁在本地栈上的元素。

能不能在comple后面加&，即返回comple的引用。这样做是不行的，因为a是在局部栈上创建的变量，当该函数结束时，局部栈被销毁，即a被销毁，那么返回的对象将指向未知的内存；

如果变量是创建在堆上，那么可以返回该变量的引用，因为堆上的变量时需要程序员手动销毁的。

分类: 编程相关 标签: ,

POJ 1182 食物链 C版本

2010年4月16日 没有评论

并查集的应用

阅读全文...

分类: 解题报告 标签: ,

POJ 1979 Red and Black C++版

2010年4月15日 没有评论

广度优先搜索的应用

阅读全文...

分类: 解题报告 标签: ,

POJ 1065 Wooden Sticks C++版本

2010年4月10日 没有评论

贪心算法的运用
阅读全文...

分类: 解题报告 标签: ,

常用四种排序算法实现 C版本

2010年3月28日 没有评论

鉴于各种排序算法经常使用，把上学期c实践课实现冒泡排序，插入排序，快速排序，希尔排序的算法贴出来供参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

 #include<stdio.h>
#include<stdlib.h>
#define MAX 200
int a[MAX];
 
void randsee();
void print(); 
void bubblesort();
void insertsort();
void quickSort(int a[],int left,int right);
int SortGroup(int pnData[], int nLen, int nBegin,int nStep);
int ShellSort(int pnData[], int nLen);
 
/*主函数*/
int main()
{
     int num=0;
     while(1)
     {
          system("cls");
          printf("1：生成随机数\n2：冒泡排序\n3；插入排序\n4；快速排序\n5；希尔排序\n6：打印随机数\n7：退出\nInput 1-7:\n");
          scanf("%d",&num);
          switch(num)
          {
          case 1:
               system("cls");
               randsee();
               system("pause");
               break;
          case 2:
               system("cls");
               bubblesort();
               system("pause");
               system("cls");
               break;
          case 3:
               system("cls");
               insertsort();
               system("pause");
               system("cls");
               break;
          case 4:
               system("cls");
               quickSort(a,0,MAX-1);
               system("pause");
               system("cls");
               break;
          case 5:
               system("cls");
               ShellSort(a,MAX);
               system("pause");
               system("cls");
               break;
          case 6:
               system("cls");
               print();
               system("pause");
               system("cls");
               break;
          case 7:
               exit(0);
          default:
               system("cls");
               printf("1：生成随机数\n2：冒泡排序\n3；插入排序\n4；快速排序\n5；希尔排序\n6：打印随机数\n7：退出\nInput 1-7:\n");
               break; 
          }
     }
     system("pause");
     return 0;
}
 
/*产生随机数组*/
void randsee()
{
     int i;
     srand(time(0));
     for(i=0;i<MAX;i++)
     {
          a[i]=1+(rand()%MAX);
     }
}
/*打印随机数*/
void print()
{
     int i;
     for(i=1;i<=MAX;++i)
     {
          printf("%5d ",a[i-1]);
          if(i%10==0)
          {
               printf("\n");
          }
     }
}
/*冒泡排序*/
void bubblesort()
{
     int i,sign,j,temp;
     for(i=0;i<MAX-2;i++)
     {
          sign=1;
          for(j=MAX-1;j>=i;j--)
          {
               if(a[j+1]<a[j])
               {
                    temp=a[j+1];
                    a[j+1]=a[j];
                    a[j]=temp;
                    sign=0;
               }
          }
          if(sign)
          {
               break;
          }
     }
}
 
/*插入排序*/
void insertsort()
{
     int i,j,c;
     for(i=1;i<MAX;++i)
     {
          c=a[i];
          j=i-1;
          while(j>=0&&a[j]>c)
          {
               a[j+1]=a[j];
               j--;
          }
          a[j+1]=c;
     }
}
 
 
/*快速排序*/
void quickSort(int a[],int left,int right)
{
     int i,j,temp;
     i=left;
     j=right;
     temp=a[left];
     if(left>right)
          return;
     while(i!=j)
     {
          while(a[j]>=temp && j>i)
               j--;
          if(j>i)
               a[i++]=a[j];
          while(a[i]<=temp && j>i)
               i++;
          if(j>i)
               a[j--]=a[i];
 
     }
     a[i]=temp;
     quickSort(a,left,i-1);
     quickSort(a,i+1,right);
}
 
 
int SortGroup(int pnData[], int nLen, int nBegin,int nStep)
{
     int i,j,k,nTemp;
     for (i = nBegin + nStep; i < nLen; i += nStep)
     {
          for (j = nBegin; j < i; j+= nStep)
          {
               if (pnData[i] < pnData[j])
               {
                    nTemp = pnData[i];
                    for (k = i; k > j; k -= nStep)
                    {
                         pnData[k] = pnData[k - nStep];
                    }
                    pnData[j] = nTemp;
               }
          }
     }
     return 1;
}
/*希尔排序*/
int ShellSort(int pnData[], int nLen)
{
     int nStep,i;
     for (nStep = nLen / 2; nStep > 0; nStep /= 2)
     {
          for (i = 0 ;i < nStep; ++i)
          {
               SortGroup(pnData, nLen, i, nStep);
          }
     }
     return 1;
}
分类: 编程相关 标签: ,

分治法求数组中第k大的元素 C++版本

2010年3月28日 没有评论

分治法求数组中第k大的元素

思想：用快速排序定位数组中其中一个元素a按从小到大确定它在数组中的位置temp

当temp等于k时，那么这个元素就是我们要找的第k个大的元素

当temp大于k时，说明第k大的元素一定在a元素的左边，向左缩小查找范围

当temp小于k时，说明第k大的元素一定在a元素的右边，向右缩小查找范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include "stdafx.h"
#include <iostream>
using namespace std;
 
int quickSort(int *a,int left,int right);
int search(int *a,int i,int j,int k);
 
//主函数
int _tmain(int argc, _TCHAR* argv[])
{
     int n,k_max;
     int a[100];
     cin >> n ;
 
     for (int i = 1; i <= n; ++i)
     {     
          cin >> a[i];
     }
     cin >> k_max;
     cout << search(a,1,n,k_max)<<endl;
 
     return 0;
}
 
//一次快速排序，返回被定位元素的位置
int quickSort(int *a,int left,int right)
{
     int i,j,temp;
     i=left;
     j=right;
     temp=a[left];
     if(left>right)
          return -1;
     while(i!=j)
     {
          while(a[j]>=temp && j>i)
               j--;
          if(j>i)
               a[i++]=a[j];
          while(a[i]<=temp && j>i)
               i++;
          if(j>i)
               a[j--]=a[i];
 
     }
     a[i]=temp;
     return i;
}
 
//分治查找第k大的元素
int search(int *a,int i,int j,int k)
{
     int temp;
     if (j < i)
     {
          return -1;
     }
     if (i == j)
     {
          return a[i];
     }
     //得到第i个元素被定位的下标
     temp = quickSort(a,i,j);
     //相等说明找到第k个大的元素
     if (temp == k)
     {
          return a[k];
     }
     //比k大，往左缩小查找范围
     else if (temp > k )
     {
          return search(a,i,temp-1,k);
     }
     //比k大，往右缩小超找范围
     else 
     {
          return search(a,temp+1,j,k-temp);
     }
}
分类: 编程相关 标签: ,

POJ 1860 Currency Exchange C版本

2009年12月22日 4 条评论

最短单源路径与松弛定理的运用

阅读全文...

分类: 解题报告 标签: ,