实验要求
采用贪心法实现：
设计原理
算法正确性证明
核心代码
void SelectIcon(double y,int n)
{
if(y>0&&n>=0)
{
double v = pow(p, n - 1);
if (y >= v)
{
icon i;
i.num = y / v;
i.value = v;
y -= i.num*i.value;
Icon.push_back(i);
}
n--;
SelectIcon(y, n);
}
}实验结果
算法时间复杂度分析
实验总结
由于题目中最小币值已经给定，v_1=1，此算法只对p为整数，总钱数y为正整数的情况有效。
当p、y至少有一个为小数时，根据贪心法的思想，从币值最大的开始找钱币，最后很有可能出现剩余钱数y_i小于v_1的情况，即此解非正确解。