找到程序背后的数学技巧 [英] Find the mathematic trick behind the program
问题描述
我创建了以下程序。
它读取一组数字并进行处理（稍后会显示）。
我的问题是这个。如果你自己测试这个程序，你会发现在每一个传递中都有一个数字 ==>
这个数字是这个传球中三个中的最小值。根据我的程序完成所有可能的组合后，我们会生成这些最小数字。
但是有些数字会重复生成。主要问题是：
有没有办法找到多少次会产生多少次数，所以我们可以跳过很多次通过，从而降低了程序的复杂性？
以下是代码：
#include< stdio.h中>
#include< stdlib.h>
#include< limits.h>
#define min（ProfitA，ProfitB，ProfitC）ProfitA> （ProfitB> ProfitC？ProfitB：ProfitC）？ ProfitA :( ProfitB> ProfitC？ProfitB：ProfitC）
int sumc（ int * array， int start， int end）{
int sum = 0 ;
while （start！= end）{
sum + = array [start];
start ++;
}
return sum;
}
int main（）
{
int N = 8 ;
int array [N] = { 8 ， 2 ， 3 ， 6 ， 5 ， 4 ， 8 ， 2 }
int Min = 0 ;
int bestA = 0 ，bestB = 0 ，bestMin = INT_MAX;
int A = 0 ，B = A + 1 ;
int i = 0 ;
int ProfitA = 0 ，ProfitB = 0 ，ProfitC = 0 ;
int * pA;
pA =& array [A];
int * pB;
pB =& array [A];
int * pC;
pC =& array [A];
ProfitC = sumc（数组，B + 1 ，N）;
for （A = 0 ; A < N - 2 ; ++ A）{
ProfitA + = *（pA + A）;
for （B = A + 1 ; B < N - 1 ; ++ B）
{
ProfitB + = *（pB + B ）;
Min = min（ProfitA，ProfitB，ProfitC）;
if （Min < bestMin）{
bestA = A，bestB = B，bestMin = Min;
}
printf（ ％2d，％2d或（％3d，％3d，％3d），A，B，ProfitA，ProfitB，ProfitC）;
for （i = 0 ; i < ; N; ++ i）
printf（ ％d％c，array [i]，（（i == A）||（i == B））？' ' ：' '）;
printf（ ==>％d \ n，Min）;
ProfitC - = *（pC + B + 1 ）;
}
ProfitB = 0 ;
ProfitC = sumc（数组，A + 3 ，N）;
}
printf（ ％d \ n ，bestMin）;
}
这是ouptut。我只关心那些最大数字。很抱歉我的描述不好，但我通过这种方式制作程序，以便您通过阅读来理解。欲了解更多信息，请发表评论！如果您看到 | 代表块，那么我们就可以赚取总和。
输出：
0,1或（1,6,28）1 | 6 | 10 3 9 6 ==> 28
0,2或（1,16,18）1 | 6 10 | 3 9 6 ==> 18
0,3或（1,19,15）1 | 6 10 3 | 9 6 ==> 19
0,4或（1,28,6）1 | 6 10 3 9 | 6 ==> 28
1,2或（7,10,18）1 6 | 10 | 3 9 6 ==> 18
1,3或（7,13,15）1 6 | 10 3 | 9 6 ==> 15
1,4或（7,22,6）1 6 | 10 3 9 | 6 ==> 22
2,3或（17,3,15）1 6 10 | 3 | 9 6 ==> 17
2,4或（17,16,6）1 6 10 | 3 9 | 6 ==> 17
3,4或（20,9,6）1 6 10 3 | 9 | 6 ==> 20
最佳最佳解决方案是15
我使用的alorythm来找到我们的东西需要。我只是用指针替换Sum函数，因为我们在每次添加指针值时只移动一个值来纠正和：
N = ...
薪资[0 ... N-1] = ...
最小值=总和（薪水[0 ... N-1]）$ b $ b表示A = 1到N-2做循环
为B = 1到N-1-A做循环
ProfitA = Sum（薪水[0 ... A-1]）$ b $ b ProfitB = Sum（Salary） [A ... A + B-1]）$ b $ b ProfitC =总和（薪水[A + B ... N-1]）$ b $ b ProfitMax =最高（ProfitA，ProfitB，ProfitC）
如果Min大于ProfitMax则
Min = ProfitMax
end if
end loop
end loop
打印Min：Permutation
编写粘性和模糊代码的好工作。
由于您的常量输入数组，您可以预先计算所有循环的Profit *。 A，B和C链接在一起吗？
我的建议是制作min宏的功能并使用一些if和braces并抛出pA，pB和PC。
用于访问数组数据：
ProfitA + = pA [A];
I have created the following program.
It reads an array of numbers and making a process (which shows later in question).
My problem is this. If you test the program on your own, you'll see that in every pass there is a number next to ==>
This number is the minimum of the three in this pass. Following all the possible combinations based on my program we produce those minimum numbers.
But there are numbers which repeately produced. The main question is this:
Is there any way to find how many numbers will be produced more than one time so we can skip many passes droping the complexity of my programm?
Here is the code :
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define min(ProfitA,ProfitB,ProfitC) ProfitA > (ProfitB > ProfitC ? ProfitB : ProfitC) ? ProfitA : (ProfitB > ProfitC ? ProfitB : ProfitC)
int sumc(int *array, int start, int end) {
int sum = 0;
while (start != end) {
sum += array[start];
start++;
}
return sum;
}
int main()
{
int N = 8;
int array[N] = {8,2,3,6,5,4,8,2}
int Min = 0;
int bestA = 0, bestB = 0, bestMin = INT_MAX;
int A = 0, B = A + 1;
int i = 0;
int ProfitA = 0, ProfitB = 0, ProfitC = 0;
int *pA;
pA = &array[A];
int *pB;
pB = &array[A];
int *pC;
pC = &array[ A ];
ProfitC = sumc(array,B + 1, N );
for ( A = 0; A < N - 2; ++A){
ProfitA += *(pA + A) ;
for ( B = A + 1; B < N - 1; ++B)
{
ProfitB += *(pB + B);
Min = min(ProfitA,ProfitB,ProfitC);
if( Min < bestMin ) {
bestA = A, bestB = B, bestMin = Min;
}
printf( "%2d,%2d or (%3d,%3d,%3d) ", A, B, ProfitA, ProfitB, ProfitC );
for( i = 0; i < N; ++i )
printf( "%d%c", array[i], ( ( i == A ) || ( i == B ) ) ? '' : ' ' );
printf( " ==> %d\n", Min);
ProfitC -= *(pC + B + 1 );
}
ProfitB = 0;
ProfitC = sumc(array, A + 3, N );
}
printf("%d\n", bestMin);
}
And here is the ouptut. I care only for the minimum of those maxinum numbers. Sorry for my bad description, but I make the programm that way so you can understand by reading it. For further info make a comment! If you see | represents blocks so we can make the sum.
Output:
0, 1 or ( 1, 6, 28) 1|6|10 3 9 6 ==> 28 0, 2 or ( 1, 16, 18) 1|6 10|3 9 6 ==> 18 0, 3 or ( 1, 19, 15) 1|6 10 3|9 6 ==> 19 0, 4 or ( 1, 28, 6) 1|6 10 3 9|6 ==> 28 1, 2 or ( 7, 10, 18) 1 6|10|3 9 6 ==> 18 1, 3 or ( 7, 13, 15) 1 6|10 3|9 6 ==> 15 1, 4 or ( 7, 22, 6) 1 6|10 3 9|6 ==> 22 2, 3 or ( 17, 3, 15) 1 6 10|3|9 6 ==> 17 2, 4 or ( 17, 12, 6) 1 6 10|3 9|6 ==> 17 3, 4 or ( 20, 9, 6) 1 6 10 3|9|6 ==> 20 The optimal best solution is 15
The alorythm I use to find what we need. I just replaced the Sum function with pointers as we move only one value at the time we add the pointee value to correct sum every time:
N = ...
Salary[0...N-1] = ...
Min = Sum(Salary[0...N-1])
for A=1 to N-2 do loop
for B=1 to N-1-A do loop
ProfitA = Sum(Salary[0...A-1])
ProfitB = Sum(Salary[A...A+B-1])
ProfitC = Sum(Salary[A+B...N-1])
ProfitMax = Max(ProfitA, ProfitB, ProfitC)
if Min is greater than ProfitMax then
Min = ProfitMax
end if
end loop
end loop
Print Min : PermutationNice job writing sticky and obscure code.
Because of your constant input array you can precompute the Profit* for all loops. Arent A, B and C chained together?
My tip is to make a function of the min macro and use some if and braces and throw out the pA, pB and pC.
For accessing the array data:
ProfitA += pA[A];
这篇关于找到程序背后的数学技巧的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
